اهو ٻڌائڻ لاءِ ڪوڊ لکو ته ڇا ٻه وڻ هڪجهڙا آهن


تڪليف جي سطح آسان
بار بار پڇڻ ۾ Amazon حقيقت جو جائزو فاتح اي صحت Microsoft جي PayPal
بائنري وڻ وڻن

مسئلو ”ڪوڊ لکو اهو معلوم ڪرڻ لاءِ ته ٻه وڻ هڪجهڙا آهن” ٻڌائي ٿو ته توهان کي ٻه بائنري وڻ ڏنا ويا آهن. اهو ڳولهيو ته اهي هڪجهڙا آهن يا نه؟ هتي ، هڪجهڙائي واري وڻ جو مطلب آهي ته ٻنهي بائنرن وڻ هڪ ئي نوڊس جي قيمت آهي نوڊس جي هڪ ئي ترتيب سان.

مثال

اهو ٻڌائڻ لاءِ ڪوڊ لکو ته ڇا ٻه وڻ هڪجهڙا آهن

Both trees are identical.

وضاحت

ٻنهي وڻن ۾ ساڳيا قدر آهن جوڙ. انهي سان گڏ انهن جو ساڳيو نوڊ ترتيب آهي. ان ڪري ٻئي وڻ هڪجهڙا آهن.

چرچو

A بائنري وڻ صرف ٻن ٻارن جي ھر ھڪ لاءِ. هاڻ اسان کي بائنري وڻ جا ٻه givenانچا ڏنا ويا آهن ، ۽ اسان کي اهو جانچڻ جي ضرورت آهي ته ڇا ٻئي وڻ هڪجهڙا آهن. اسان سڏيندا ٻه وڻ هڪجهڙا آهن جيڪڏهن انهن وٽ نوڊس جو هڪ ئي بندوبست آهي. ساڳئي ترتيب سان ، اسان جو مطلب اهو آهي ته جيڪڏهن ڪجهه نوڊ ڪجهه نوڊ جي کاٻي پاسي ۾ آهي. انهن کي ٻئي وڻ ۾ هڪ ئي ترتيب هجڻ گهرجي. جيڪڏھن ٻنھي وڻن جو ھڪ ئي بندوبست آھي ، انھن سڀني وڻن ۾ ھڪڙي ھڪ ٻئي لاءِ ساڳيا قدر وڌائڻ گهرجن.

هاڻي اسان knowاڻون ٿا ته ڪهڙي وڻ کي هڪجهڙائي سڏيو وڃي ٿو. سو هاڻي اسان اهو رستو ڳولڻ جي ڪوشش ڪنداسين ته ٻن ڏنل وڻ هڪجهڙا آهن. طريقو سادو آهي. اسان کي وڻن کي لهرائڻ جي ضرورت آهي. وڻ کي ڇڪڻ دوران ، اسان چڪاس ڪندا رهون ٿا ته ڇا پهرين وڻ جو هاڻوڪو نوڊ ساڳيو ئي ٻئي وڻ جو آهي. جيڪڏهن اهي مختلف آهن ، ته اهي هڪجهڙا نه آهن. توڙي جو انهن جا ڪجهه مختلف انتظام هجن. يا جيڪڏھن ھڪڙي وڻن ۾ ھڪ ٻئي جا ڳوڙھا آھن. پوءِ پڻ ، اسان اهو اندازو ڪري سگھون ٿا ساڳئي طريقي سان. ڇاڪاڻ ته جيڪڏهن ڪجهه وڻ هڪ اضافي نوڊ هو ، ته ٻيو وڻ به انهيءَ پوزيشن تي NULL قيمت وارو هوندو. ھن جو نتيجو غير شناخت وارا وڻ ھوندا. تنهن ڪري انهي طريقي سان اسين لکون ٿا اهو طئي ڪرڻ لاءِ ته ٻه وڻ هڪجهڙا آهن.

ڪوڊ

سي ++ ڪوڊ اهو معلوم ڪرڻ لاءِ ته ڇا ٻه وڻ هڪ جهڙا آهن

#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 ٻنهي وڻن ۾ گهٽ ۾ گهٽ تعداد ۾ نوڊس جو اشارو ڏئي ٿو. جتان اسان وڻن ۾ نوڊس مان ڪرايا آهن. جيڪڏهن انهن جا ساڳيا نمبر جوڙيا ويا هئا ، گهٽ ۾ گهٽ قدر ٻنهي نوڊس جي برابر آهي. پر جيڪڏهن انهن جا مختلف نمبر جوڙيا هئا ، اسان کي بدترين صورتن ۾ گهٽ ۾ گهٽ نوڊس مان لنگهڻو آهي.

خلائي پيچيدگي

اي (ايڇ) ، ڇاڪاڻ ته جيڪڏهن اسان ڪمپائلر اسٽيڪ جي گهربل جڳهه تي غور ڪريون. پوءِ گهربل جاءِ ساڳيو ئي آهي جيڪا ترتيب ڏيڻ واري کان ورتي وڃي ٿي.