برای تعیین یکسان بودن دو درخت کد را بنویسید


سطح دشواری ساده
اغلب در آمازون واقعیت متعصبان GE بهداشت و درمان مایکروسافت پی پال
درخت باینری درخت

مسئله "نوشتن کد برای تعیین اینکه دو درخت یکسان هستند" بیان می کند که دو درخت باینری به شما داده می شود. دریابید که یکسان هستند یا نه؟ در اینجا ، درخت یکسان به این معنی است که هر دو درخت باینری دارای ارزش گره یکسانی با آرایش یکسان گره ها هستند.

مثال

برای تعیین یکسان بودن دو درخت کد را بنویسید

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

کد جاوا برای تعیین یکسان بودن دو درخت

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 نشانگر حداقل تعداد گره در هر دو درخت است. از آنجا که ما گره های درختان را رد کرده ایم. اگر تعداد گره های آنها یکسان باشد ، حداقل مقدار برابر با هر دو گره است. اما اگر تعداد گره های متفاوتی داشته باشند ، در بدترین حالت باید حداقل تعداد گره ها را رد کنیم.

پیچیدگی فضا

O (H) ، زیرا اگر فضای مورد نیاز پشته کامپایلر را در نظر بگیریم. سپس فضای مورد نیاز همان فضایی است که توسط کامپایلر گرفته شده است.