Напишете код за да утврдите дали две дрвја се идентични  


Ниво на тешкотија Лесно
Често прашувано во Амазон Факти Фанатици ГЕ здравство Мајкрософт PayPal
Бинарно дрво Дрво

Проблемот „Напиши код за да утврдиш дали две дрвја се идентични“ вели дека ви се дадени две бинарни дрвја. дознајте дали се идентични или не? Овде, идентичното дрво значи дека и двете бинарни дрвја имаат иста вредност на јазол со ист распоред на јазли.

пример  

Напишете код за да утврдите дали две дрвја се идентичниПин

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 означува минимален број на јазли во обете дрвја. Бидејќи ги поминавме јазлите во дрвјата. Ако тие имале ист број на јазли, тогаш минималната вредност е иста како и на двата јазли. Но, ако тие имаа различен број на јазли, ние треба да го поминеме минималниот број на јазли во најлош случај.

Видете исто така
Збир на патеки

Комплексноста на просторот

О (H), затоа што ако го земеме предвид просторот потребен за магацинот на компајлерот. Тогаш потребниот простор е ист како оној што го презема компајлерот.