Drzewo symetryczne

Poziom trudności Łatwo
Często zadawane pytania Adobe Amazonka Apple Capital One eBay Facebook Fanatycy Google MAQ wyrocznia
Pierwsze przeszukiwanie szerokości Głębokie pierwsze wyszukiwanie Drzewoodwiedzajacy 76

Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że ​​trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.

In Drzewo symetryczne problem, który daliśmy drzewo binarnesprawdź, czy jest lustrem samego siebie. Mówi się, że drzewo jest swoim lustrzanym odbiciem, jeśli istnieje oś symetrii przechodząca przez węzeł główny, który dzieli drzewo na dwie takie same połowy.

Przykład

Drzewo symetryczneszpilka

Drzewo symetryczneszpilka

Drzewo symetryczneszpilka

Drzewo symetryczneszpilka

Drzewo symetryczneszpilka

Typy rozwiązań dla drzewa symetrycznego

  1. Rekurencyjne
  2. Iteracyjny

Rekurencyjne

Podejście

Używamy 2 kopii drzewa binarnego, powiedzmy b1 i b2 (do obsługi oddzielnie lewego i prawego poddrzewa) i sprawdzamy, czy:

  1. korzeń wartości b1 i b2 są takie same lub nie.
  2. lewo poddrzewo b1 i prawo poddrzewo b2 są takie same (zarówno pod względem struktury, jak i wartości węzłów), czy nie.
  3. prawo poddrzewo b1 i lewo poddrzewo b2 jest taka sama (zarówno pod względem struktury, jak i wartości węzłów), czy nie.

jeśli warunki 1,2, 3 i XNUMX są spełnione rekurencyjnie dla lewego i prawego poddrzewa zwracamy po prostu prawdę (w przeciwnym razie zwracamy fałsz).

b1 i b2 mają odpowiednio root1 i root2 jako węzeł główny.

Algorytm dla drzewa symetrycznego

  1. Utwórz dwie kopie drzewa binarnego (root1 i root2), aby oddzielnie obsługiwać lewe i prawe poddrzewo.
  2. Zdefiniuj przypadek podstawowy.
  3. Sprawdź, czy warunki wymienione powyżej (1,2, 3 i XNUMX) są spełnione, czy nie.
  4. Jeśli powyższe warunki są fałszywe, co oznacza, że ​​jeden z elementów root1 lub root2 jest pusty, zwróć false.

Implementacja dla Symmetric Tree

Program C ++ dla drzewa symetrycznego
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// defining the tree node
class Node
{
    public : 
    int data;
    Node *left;
    Node *right;
    
    // constructor for initialization
    Node(int num)
    {
        data = num;
        left = right = NULL;
    }
};

/*utility function to check whether trees rooted at 
root1 and root2 are mirror images of each other or not */
bool utility(Node *root1, Node *root2) 
{ 
    /* base case : if both trees are empty then 
    they are mirror images of each other */
    if (root1 == NULL && root2 == NULL) 
        return true; 
  
    /* for trees rooted at root1 and root2 to be mirror images, 
    following conditions must be satisfied */
    if (root1 && root2) 
        /* Their root node's data must be same
        if this is not the case then immediately 
        return false */
        return root1->data == root2->data &&  
                
                /*left subtree of left tree and right s
                ubtree of right tree have to be mirror images*/
                utility(root1->left, root2->right) &&   
                
                    /*right subtree of left tree and left subtree 
                    of right tree have to be mirror images*/ 
                    utility(root1->right, root2->left); 
    
    
    /* This condition is reached when : 
    if only either of root1 or root2 is empty */
    
    return false; 
} 

/* function to check if tree 
rooted at root is Symmetric */
bool isSymmetric(Node* root) 
{ 
    // apply utility function to check if tree is mirror of itself 
    return utility(root, root); 
} 

// main function to implement above functions
int main() 
{
    /* construct the binary tree*/
    Node *root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(2);
    root->left->left = new Node(3);
    root->left->right = new Node(4);
    root->right->left = new Node(4);
    root->right->right = new Node(3);
    
    isSymmetric(root) ? cout<<"Symmetric Tree" : cout<<"Not Symmetric";
    
  return 0;
}
Symmetric Tree
Program Java dla Symmetric Tree
import java.io.*;
import java.util.*;

class tutorialCup 
{
    static class Node
    {
        int data;
        Node left;
        Node right;
        
        Node(int num)
        {
            data = num;
            left = right = null;
        }
    };
    
    /*utility function to check whether trees rooted at 
    root1 and root2 are mirror images of each other or not */
    static boolean utility(Node root1, Node root2) 
    { 
        /* base case : if both trees are empty then 
        they are mirror images of each other */
        if (root1 == null && root2 == null) 
            return true; 
      
        /* for trees rooted at root1 and root2 to be mirror images, 
        following conditions must be satisfied */
        if (root1 != null && root2 != null) 
            /* Their root node's data must be same
            if this is not the case then immediately 
            return false */
            return root1.data == root2.data &&  
                    
                    /*left subtree of left tree and right s
                    ubtree of right tree have to be mirror images*/
                    utility(root1.left, root2.right) &&   
                    
                        /*right subtree of left tree and left subtree 
                        of right tree have to be mirror images*/ 
                        utility(root1.right, root2.left); 
        
        
        /* This condition is reached when : 
        if only either of root1 or root2 is empty */
        
        return false; 
    } 
    
    /* function to check if tree 
    rooted at root is Symmetric */
    static boolean isSymmetric(Node root) 
    { 
        // apply utility function to check if tree is mirror of itself 
        return utility(root, root); 
    } 
    
    /* main function to implement above function */
    public static void main (String[] args) 
    {
        /* construct the binary tree*/
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(2);
        root.left.left = new Node(3);
        root.left.right = new Node(4);
        root.right.left = new Node(4);
        root.right.right = new Node(3);
        
        if(isSymmetric(root))
        System.out.println("Symmetric Tree");
        else System.out.println("Not Symmetric");
    }

}
Symmetric Tree

Analiza złożoności

  1. Złożoność czasowa: T (n) = O (n)
  2. Złożoność przestrzeni: A (n) = O (1) lub O (log n), biorąc pod uwagę przestrzeń stosu rekurencji.

Iteracyjny

Podejście

Chodzi o to, aby przekonwertować podejście rekurencyjne na podejście iteracyjne przy użyciu pliku kolejka strukturę danych, wykonując przeszukiwanie wszerz (BFS)/przechodzenie do kolejności poziomów. Ponownie, używamy 2 kopii drzewa binarnego, powiedzmy b1 i b2 (aby obsługiwać oddzielnie lewe i prawe poddrzewo) i sprawdzamy, czy:

  1. korzeń wartości b1 i b2 są takie same lub nie.
  2. lewo poddrzewo b1 i prawo poddrzewo b2 są takie same (zarówno pod względem struktury, jak i wartości węzłów), czy nie.
  3. prawo poddrzewo b1 i lewo poddrzewo b2 są takie same (zarówno pod względem struktury, jak i wartości węzłów), czy nie.

jeśli warunki 1,2, 3 i XNUMX są prawdziwe Iteracyjnie prawdziwe dla lewego i prawego poddrzewa, po prostu zwracamy prawdę (w przeciwnym razie zwracamy fałsz).

b1 i b2 mają odpowiednio root1 i root2 jako węzeł główny.

Algorytm dla drzewa symetrycznego

  1. Zdefiniuj przypadki podstawowe.
  2. Utwórz kolejkę i wepchnij do niej dwie kopie węzła głównego (do obsługi lewego i prawego poddrzewa).
  3. Rozpocznij przechodzenie BFS i przy każdej iteracji zdejmij dwa węzły z kolejki, a mianowicie leftNode i rightNode.
    • jeśli wartość obu węzłów nie jest równa, zwróć false (i zakończ przemierzanie).
    • Następnie, jeśli leftNode.left i rightNode.right obie nie mają wartości null, wepchnij je do kolejki.
      • jeśli tylko jedno z powyższych nie ma wartości null, zwróci false (i zakończ przemierzanie).
    • Następnie, jeśli leftNode.right i rightNode.left nie są zerowe, wepchnij je do kolejki.
      • jeśli tylko jedno z powyższych nie jest zerowe, zwraca false (i przerywa przemierzanie).
  4. Jeśli kolejka stanie się pusta, BFS zostanie zakończony i zwróci wartość true.

1 przykład

szpilka szpilkaszpilka

 

2 przykład

szpilka   szpilka

Implementacja dla Symmetric Tree

Program C ++ dla drzewa symetrycznego
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// defining the tree node
class Node
{
    public : 
    int data;
    Node *left;
    Node *right;
    
    // constructor for initialization
    Node(int num)
    {
        data = num;
        left = right = NULL;
    }
};

/* function to check if tree 
rooted at root is Symmetric */
bool isSymmetric(Node* root) 
{
    /* base cases */
    
    // 1. if tree is empty it's symmetric
    if(root == NULL) 
        return true; 
    
    // 2. if tree has only one node, it's symmetric
    if(!root->left && !root->right) 
        return true; 
    
    // create queue for BFS traversal  
    queue <Node*> q; 
    
    /* root is inserted two times so that we can peform
    bi-directional BFS to check mirror image property
    which is basically a type of bilateral symmetry */
    q.push(root); 
    q.push(root); 
      
    /* these store nodes for bi-directional BFS traversal */
    Node* leftNode, *rightNode; 
      
    while(!q.empty())
    { 
        /* remove nodes to check if they are symmetric or not */ 
        leftNode = q.front(); 
        q.pop(); 
          
        rightNode = q.front(); 
        q.pop(); 
          
        /* if both left and right nodes exist but 
        have different, the tree is not symmetric */ 
        if(leftNode->data != rightNode->data) 
        return false; 
          
        /* Push left child of left subtree node 
        and right child of right subtree 
        node in queue */ 
        if(leftNode->left && rightNode->right)
        { 
            q.push(leftNode->left); 
            q.push(rightNode->right); 
        } 
          
        /* Else if only one child is present alone 
        and other is NULL, then tree is not symmetric */ 
        else if (leftNode->left || rightNode->right) 
        return false; 
          
        /* Push right child of left subtree node 
        and left child of right subtree node 
        in queue */ 
        if(leftNode->right && rightNode->left)
        { 
            q.push(leftNode->right); 
            q.push(rightNode->left); 
        } 
        /* Else if only one child is present alone 
        and other is NULL, then tree is not symmetric */ 
        else if(leftNode->right || rightNode->left) 
        return false; 
    } 
    
    /* the tree is symmetric if all the nodes 
    have been processed and queue becomes empty */
    
    return true; 
} 

// main function to implement above functions
int main() 
{
    /* construct the binary tree*/
    Node *root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(2);
    root->left->left = new Node(3);
    root->left->right = new Node(4);
    root->right->left = new Node(4);
    root->right->right = new Node(3);
    
    isSymmetric(root) ? cout<<"Symmetric Tree" : cout<<"Not Symmetric";
    
  return 0;
}
Symmetric Tree
Program Java dla Symmetric Tree
import java.io.*;
import java.util.*;

class tutorialCup 
{
    static class Node
    {
        int data;
        Node left;
        Node right;
        
        Node(int num)
        {
            data = num;
            left = right = null;
        }
    };
    
    /* function to check if tree 
    rooted at root is Symmetric */
    static boolean isSymmetric(Node root) 
    {
        /* base cases */
        
        // 1. if tree is empty it's symmetric
        if(root == null) 
            return true; 
        
        // 2. if tree has only one node, it's symmetric
        if(root.left == null && root.right == null) 
            return true; 
        
        // create queue for BFS traversal  
        Queue <Node> q = new LinkedList<>(); 
        
        /* root is inserted two times so that we can peform
        bi-directional BFS to check mirror image property
        which is basically a type of bilateral symmetry */
        q.add(root); 
        q.add(root); 
          
        /* these store nodes for bi-directional BFS traversal */
        Node leftNode, rightNode; 
          
        while(!q.isEmpty())
        { 
            /* remove nodes to check if they are symmetric or not */ 
            leftNode = q.poll();
            rightNode = q.poll();
              
            /* if both left and right nodes exist but 
            have different, the tree is not symmetric */ 
            if(leftNode.data != rightNode.data) 
            return false; 
              
            /* Push left child of left subtree node 
            and right child of right subtree 
            node in queue */ 
            if(leftNode.left != null && rightNode.right != null)
            { 
                q.add(leftNode.left); 
                q.add(rightNode.right); 
            } 
              
            /* Else if only one child is present alone 
            and other is NULL, then tree is not symmetric */ 
            else if (leftNode.left != null  || rightNode.right != null) 
            return false; 
              
            /* Push right child of left subtree node 
            and left child of right subtree node 
            in queue */ 
            if(leftNode.right != null && rightNode.left != null)
            { 
                q.add(leftNode.right); 
                q.add(rightNode.left); 
            } 
            /* Else if only one child is present alone 
            and other is NULL, then tree is not symmetric */ 
            else if(leftNode.right != null || rightNode.left != null) 
            return false; 
        } 
        
        /* the tree is symmetric if all the nodes 
        have been processed and queue becomes empty */
        
        return true; 
    } 

    
    /* main function to implement above function */
    public static void main (String[] args) 
    {
        /* construct the binary tree*/
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(2);
        root.left.left = new Node(3);
        root.left.right = new Node(4);
        root.right.left = new Node(4);
        root.right.right = new Node(3);
        
        if(isSymmetric(root))
        System.out.println("Symmetric Tree");
        else System.out.println("Not Symmetric");
    }

}
Symmetric Tree

Analiza złożoności

  1. Złożoność czasowa: T (n) = O (n)
  2. Złożoność przestrzeni: A (n) = O (n), używana jest kolejka.

Referencje

Wywiady dotyczące projektowania systemu pękania
Translate »