Напішыце код, каб вызначыць, ці аднолькавыя два дрэвы


Узровень складанасці Лёгка
Часта пытаюцца ў амазонка Факты Фанатыкі GE Healthcare Microsoft PayPal
Двайковае дрэва дрэва

Праблема «Напісаць код, каб вызначыць, ці аднолькавыя два дрэвы» абвяшчае, што вам дадзены два бінарныя дрэвы. даведацца, аднолькавыя яны ці не? Тут ідэнтычнае дрэва азначае, што абодва бінарныя дрэвы маюць аднолькавае значэнне вузла з аднолькавым размяшчэннем вузлоў.

Прыклад

Напішыце код, каб вызначыць, ці аднолькавыя два дрэвы

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

Аналіз складанасці

Часовая складанасць

O (N), дзе N абазначае мінімальную колькасць вузлоў у абодвух дрэвах. Так як мы перасеклі вузлы на дрэвах. Калі яны мелі аднолькавую колькасць вузлоў, то мінімальнае значэнне такое ж, як у абодвух вузлоў. Але калі ў іх была розная колькасць вузлоў, мы павінны перасекчы мінімальную колькасць вузлоў у горшым выпадку.

Касмічная складанасць

O (H), таму што калі ўлічыць месца, неабходнае для стэка кампілятара. Тады неабходная прастора такая ж, як і ў кампілятара.