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


Ниво тешкоће Лако
Често питани у амазонка Фацтсет Фанатици ГЕ Хеалтхцаре мицрософт ПаиПал
Бинарно дрво Дрво

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

Пример  

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

Both trees are identical.

Објашњење

Оба стабла имају чворове исте вредности. Такође, имају исти распоред чворова. Дакле, оба стабла су идентична.

Приступ  

A бинарно стабло има само двоје деце за сваки од чворова. Сада смо добили два корена бинарног стабла и морамо проверити да ли су оба стабла идентична. Два стабла називамо идентичним ако имају исти распоред чворова. Под истим распоредом подразумевамо да ако је неки чвор у левом смеру од неког чвора. Морају бити у истом распореду на другом дрвету. Ако оба стабла имају исти распоред, треба да имају исту вредност за сваки од одговарајућих чворова у оба стабла.

Сада знамо како се дрвеће назива идентичним. Па ћемо сада покушати да смислимо начин да проверимо да ли су два дата дрвета идентична. Метода је једноставна. Морамо прећи дрвеће. док обилазимо дрво, настављамо да проверавамо да ли је тренутни чвор првог стабла исти као и чвор другог стабла. Ако се разликују, онда нису идентични. Чак и ако имају другачије аранжмане. Или ако је једно дрво имало додатне чворове у поређењу са другим. Тада такође то можемо схватити истим методом. јер ако је неко дрво имало додатни чвор, онда ће друго дрво на тој позицији имати НУЛЛ вредност. То ће резултирати неидентичним стаблима. Дакле, тако пишемо код да бисмо утврдили да ли су два стабла идентична.

Види такође
Решење са бројем допуна броја

код  

Ц ++ код за утврђивање да ли су два стабла идентична

#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

Јава код за утврђивање да ли су два стабла идентична

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

Анализа сложености  

Временска сложеност

НА), где Н означава минимални број чворова у оба стабла. Пошто смо прешли чворове на дрвећу. Ако су имали једнак број чворова, тада је минимална вредност иста као оба чвора. Али ако су имали различит број чворова, у најгорем случају морамо прећи минимални број чворова.

Види такође
Патх Сум

Сложеност простора

О (Х), јер ако узмемо у обзир простор потребан за стек компајлера. Тада је потребан простор исти оном који је заузео компајлер.