대칭 트리

난이도 쉽게
자주 묻는 질문 어도비 벽돌 아마존 Apple 자본 하나 이베이 Facebook 광신자 구글 MAQ 신탁
폭 우선 검색 깊이 우선 검색 나무조회수 77

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

In 대칭 트리 우리가 준 문제 이진 트리, 자신의 거울인지 확인하십시오. 나무를 두 개의 동일한 절반으로 나누는 루트 노드를 통해 대칭 축이있는 경우 나무는 그 자체의 거울 이미지라고합니다.

대칭 트리

대칭 트리

대칭 트리

대칭 트리

대칭 트리

대칭 트리에 대한 솔루션 유형

  1. 재귀
  2. 반복적 인

재귀

접근

우리는 b2과 b1 (왼쪽 및 오른쪽 하위 트리를 개별적으로 처리하기 위해)와 같이 이진 트리의 복사본 2 개를 사용하고 다음 사항을 확인합니다.

  1. 뿌리 b1과 b2의 값이 같거나 같지 않습니다.
  2. 왼쪽 (left) 하위 트리 b1연락해주세요 하위 트리 b2 동일하거나 (구조 및 노드 값 측면에서) 동일하지 않습니다.
  3. 연락해주세요 하위 트리 b1왼쪽 (left) 하위 트리 b2 동일하거나 (구조 및 노드 값 측면에서) 동일하지 않습니다.

조건 1,2 및 3이 참인 경우 재귀 적으로 왼쪽 및 오른쪽 하위 트리의 경우 단순히 true를 반환합니다 (그렇지 않으면 false를 반환).

b1과 b2는 각각 root1과 root2를 루트 노드로 가지고 있습니다.

대칭 트리 알고리즘

  1. 이진 트리 (root1root2)를 사용하여 왼쪽 및 오른쪽 하위 트리를 별도로 처리합니다.
  2. 기본 케이스를 정의하십시오.
  3. 위에 언급 된 조건 (1,2 및 3)이 참인지 확인하십시오.
  4. 위 조건이 false이면 root1 또는 root2 중 하나가 비어 있으면 false를 반환합니다.

대칭 트리 구현

대칭 트리 용 C ++ 프로그램
#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
대칭 트리 용 Java 프로그램
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

복잡성 분석

  1. 시간 복잡도 : T (n) = O (n)
  2. 공간 복잡성 : 재귀 스택 공간을 고려한 A (n) = O (1) 또는 O (log n).

반복적 인

접근

아이디어는 다음을 사용하여 재귀 적 접근 방식을 반복적 접근 방식으로 변환하는 것입니다. 폭 우선 검색 (BFS)/레벨 순서 순회. 다시 말하지만, 우리는 b2과 b1 (왼쪽 및 오른쪽 하위 트리를 개별적으로 처리하기 위해)와 같이 이진 트리의 복사본 2 개를 사용하고 다음 사항을 확인합니다.

  1. 뿌리 b1과 b2의 값이 같거나 같지 않습니다.
  2. 왼쪽 (left) 하위 트리 b1연락해주세요 하위 트리 b2 동일하거나 (구조 및 노드 값 측면에서) 동일하지 않습니다.
  3. 연락해주세요 하위 트리 b1왼쪽 (left) 하위 트리 b2 동일하거나 (구조 및 노드 값 측면에서) 동일하지 않습니다.

조건 1,2 및 3이 참이면 왼쪽 및 오른쪽 하위 트리에 대해 반복적으로 참이면 참을 반환합니다 (그렇지 않으면 거짓을 반환합니다).

b1과 b2는 각각 root1과 root2를 루트 노드로 가지고 있습니다.

대칭 트리 알고리즘

  1. 기본 사례를 정의합니다.
  2. 큐를 만들고 루트 (왼쪽 및 오른쪽 하위 트리를 처리하기 위해) 노드의 두 복사본을 여기에 푸시합니다.
  3. BFS 순회를 시작하고 각 반복에서 큐에서 leftNode 및 rightNode라는 두 개의 노드를 팝합니다.
    • 두 노드의 값이 같지 않으면 false를 반환하고 순회를 종료합니다.
    • 그런 다음 leftNode.left 및 rightNode.right가 모두 null이 아닌 경우 큐로 푸시합니다.
      • 위 중 하나만 null이 아니면 false를 반환하고 순회를 종료합니다.
    • 그런 다음 leftNode.right 및 rightNode.left 둘 다 null이 아닌 경우 큐로 푸시합니다.
      • 위 중 하나만 null이 아니면 false를 반환하고 순회를 종료합니다.
  4. 대기열이 비게되면 BFS가 종료되고 true를 반환합니다.

예제 1

 

예제 2

  

대칭 트리 구현

대칭 트리 용 C ++ 프로그램
#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
대칭 트리 용 Java 프로그램
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

복잡성 분석

  1. 시간 복잡도 : T (n) = O (n)
  2. 공간 복잡성 : A (n) = O (n), 대기열이 사용됩니다.

참조

균열 시스템 설계 인터뷰
Translate »