두 트리가 동일한 지 확인하는 코드 작성

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

"두 트리가 동일한 지 확인하기위한 코드 작성"문제는 두 개의 이진 트리가 제공된다는 것을 나타냅니다. 그들이 동일한 지 아닌지 알아? 여기서 동일한 트리는 두 이진 트리가 동일한 노드 배열로 동일한 노드 값을 갖는다는 것을 의미합니다.

예

핀

Both trees are identical.

설명

두 트리 모두 동일한 값을 가진 노드를 가지고 있습니다. 또한 노드 배열이 동일합니다. 따라서 두 나무는 동일합니다.

접근

A 이진 트리 각 노드에 대해 두 개의 자식 만 있습니다. 이제 이진 트리의 두 뿌리가 주어졌고 두 트리가 동일한 지 확인해야합니다. 노드 배열이 같으면 두 트리가 동일하다고 부릅니다. 같은 배열로, 어떤 노드가 어떤 노드의 왼쪽 방향에 있다면 우리는 의미합니다. 다른 트리에서 동일한 배열에 있어야합니다. 두 트리의 배열이 동일한 경우 두 트리의 각 해당 노드에 대해 동일한 값을 가져야합니다.

이제 우리는 동일한 나무가 무엇인지 압니다. 이제 우리는 주어진 두 나무가 동일한 지 확인하는 방법을 알아 내려고합니다. 방법은 간단합니다. 우리는 나무를 가로 질러야합니다. 트리를 순회하는 동안 첫 번째 트리의 현재 노드가 두 번째 트리의 노드와 동일한 지 계속 확인합니다. 서로 다르면 동일하지 않습니다. 서로 다른 배열이 있더라도. 또는 트리 중 하나에 다른 노드와 비교하여 추가 노드가있는 경우. 그러면 우리는 같은 방법으로 그것을 알아낼 수 있습니다. 어떤 트리에 추가 노드가 있으면 다른 트리는 해당 위치에서 NULL 값을 갖기 때문입니다. 이로 인해 동일하지 않은 트리가 생성됩니다. 이것이 두 트리가 동일한 지 확인하는 코드를 작성하는 방법입니다.

암호

두 트리가 동일한 지 확인하는 C ++ 코드

#include<bits/stdc++.h>
using namespace std;

struct node {
  int data;
  node *left, *right;
};

bool identicalTree(node* root1, node* root2){
    if(root1 && root2) // if both current nodes are not null
    {
        if(root1->data == root2->data // both of the current nodes should have same value
           && identicalTree(root1->left, root2->left) // the left subtree of both the trees should also be identical
           && identicalTree(root1->right, root2->right)) // the right subtree of both the trees should also be identical
            return true;
        return false;
    }
    else if(!root1 && !root2) // if both tree have current nodes as null nodes
        return true;
    return false;
}

node* create(int data){
  node* tmp = new node();
  tmp->data = data;
  tmp->left = tmp->right = NULL;
  return tmp;
}

int main()
{
  node* root1 = create(5);
  root1->left = create(7);
  root1->right = create(3);
  root1->left->left = create(9);
  root1->left->right = create(6);
  root1->left->right->left = create(1);
  root1->left->right->right = create(4);

  node* root2 = create(5);
  root2->left = create(7);
  root2->right = create(3);
  root2->left->left = create(9);
  root2->left->right = create(6);
  root2->left->right->left = create(1);
  root2->left->right->right = create(4);

  cout<<(identicalTree(root1, root2) ? "Yes" : "No");
}

Yes

두 트리가 동일한 지 확인하는 Java 코드

import java.util.*;

class node{
  int data;
  node left, right;
}

class Main{

  static boolean identicalTree(node root1, node root2){
      if(root1 != null && root2 != null) // if both current nodes are not null
      {
          if(root1.data == root2.data // both of the current nodes should have same value
             && identicalTree(root1.left, root2.left) // the left subtree of both the trees should also be identical
             && identicalTree(root1.right, root2.right)) // the right subtree of both the trees should also be identical
              return true;
          return false;
      }
      else if(root1 == null && root2 == null) // if both tree have current nodes as null nodes
          return true;
      return false;
  }

  static node create(int data){
    node tmp = new node();
    tmp.data = data;
    tmp.left = tmp.right = null;
    return tmp;
  }

  public static void main(String[] args){
    node root1 = create(5);
    root1.left = create(7);
    root1.right = create(3);
    root1.left.left = create(9);
    root1.left.right = create(6);
    root1.left.right.left = create(1);
    root1.left.right.right = create(4);

    node root2 = create(5);
    root2.left = create(7);
    root2.right = create(3);
    root2.left.left = create(9);
    root2.left.right = create(6);
    root2.left.right.left = create(1);
    root2.left.right.right = create(4);

    System.out.print(identicalTree(root1, root2) ? "Yes" : "No");
  }
}

Yes

복잡성 분석

시간 복잡성

의 위에), 여기서 N은 두 트리의 최소 노드 수를 나타냅니다. 우리는 나무의 노드를 횡단했기 때문에. 노드 수가 동일한 경우 최소값은 두 노드의 최소값과 동일합니다. 그러나 노드 수가 다른 경우 최악의 경우 최소 노드 수를 통과해야합니다.

공간 복잡성

오), 컴파일러 스택에 필요한 공간을 고려한다면. 그러면 필요한 공간은 컴파일러가 차지하는 공간과 같습니다.