İki ağacın eynisini müəyyənləşdirmək üçün kod yazın

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon Məlumat dəsti Fanatics GE Healthcare microsoft PayPal
İkili ağac AğacBaxılıb 24

“İki ağacın eynisini müəyyənləşdirmək üçün kod yazın” problemi sizə iki ikili ağac verildiyini bildirir. eynisinin olub olmadığını öyrənin? Burada eyni ağac, hər ikili ağacın eyni qovşaq düzümü ilə eyni qovşaq dəyərinə sahib olması deməkdir.

misal

İki ağacın eynisini müəyyənləşdirmək üçün kod yazınPin

Both trees are identical.

Izahat

Hər iki ağacın eyni dəyəri olan qovşaqları var. Ayrıca, eyni düyün tənzimləmələri var. Beləliklə hər iki ağac eynidir.

Yanaşma

A ikili ağac düyünlərin hər biri üçün yalnız iki övladı var. İndi bizə ikili ağacın iki kökü verilir və hər iki ağacın eyni olub olmadığını yoxlamaq lazımdır. İki ağac eyni qovşaqlarına sahib olduqları təqdirdə eynidir. Eyni tənzimləmə ilə, hansısa bir düyün hansısa düyünün sol istiqamətindədirsə demək istəyirik. Digər ağacda eyni düzülüşdə olmaları lazımdır. Hər iki ağacın eyni düzülüşü varsa, hər iki ağacdakı müvafiq qovşaqların hər biri üçün eyni dəyərə sahib olmaları lazımdır.

İndi hansı ağacların eyni adlandırıldığını bilirik. Beləliklə, indi verilən iki ağacın eyni olub olmadığını yoxlamaq üçün bir yol tapmağa çalışacağıq. Metod sadədir. Ağacları keçməliyik. ağacdan keçərkən ilk ağacın cari düyününün ikinci ağacla eyni olub olmadığını yoxlamağa davam edirik. Fərqlidirlərsə, eyni deyillər. Bəzi fərqli tənzimləmələri olsa belə. Və ya ağaclardan birinin digərinə nisbətən əlavə qovşaqları varsa. Sonra da eyni üsulla bunu anlaya bilərik. çünki bəzi ağaclarda əlavə bir qovşaq varsa, digər ağacın bu vəziyyətdə NULL dəyəri olacaqdır. Bu, eyni olmayan ağaclarla nəticələnəcəkdir. Beləliklə, iki ağacın eyni olub olmadığını müəyyənləşdirmək üçün kod yazırıq.

Kodu

İki ağacın eyni olub olmadığını təyin etmək üçün C ++ kodu

#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

İki ağacın eynisini müəyyənləşdirmək üçün Java kodu

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

Mürəkkəblik təhlili

Zaman mürəkkəbliyi

O (N), burada N hər iki ağacdakı minimum düyün sayını göstərir. Ağaclardakı qovşaqları keçdiyimiz üçün. Eyni sayda qovşaqlara sahib idilərsə, minimum dəyər hər iki qovşaqdakı ilə eynidir. Ancaq fərqli bir qovşaq sayı olsaydı, ən pis vəziyyətdə minimum qovşaq sayını keçməliyik.

Kosmik Mürəkkəblik

O (H), çünki kompilyator yığını üçün lazım olan yeri nəzərə alsaq. Sonra tələb olunan yer tərtibçinin götürdüyü ilə eynidir.

Translate »