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


난이도 쉽게
자주 묻는 질문 아마존 팩트 셋 광신자 GE 헬스 케어 Microsoft 페이팔
이진 트리 나무

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

예  

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

Both trees are identical.

설명

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

접근  

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

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

참조
숫자 보완 Leetcode 솔루션

암호  

두 트리가 동일한 지 확인하는 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은 두 트리의 최소 노드 수를 나타냅니다. 우리는 나무의 노드를 횡단했기 때문에. 노드 수가 동일한 경우 최소값은 두 노드의 최소값과 동일합니다. 그러나 노드 수가 다른 경우 최악의 경우 최소 노드 수를 통과해야합니다.

참조
경로 합계

공간 복잡성

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