कोड लिनुहोस् निर्धारण गर्नका लागि यदि दुई रूखहरू समान छन्


कठिनाई तह सजिलो
बारम्बार सोधिन्छ अमेजन तथ्य कट्टरपन्थी जीई हेल्थकेयर माइक्रोसफ्ट 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

जाभा कोड निर्धारण गर्नका लागि यदि दुई रूखहरू समान छन्

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), जहाँ एन दुबै रूखहरूमा नोडहरूको न्यूनतम संख्या जनाउँछ। हामीले रूखहरूमा नोडहरू पार गरेका छौं। यदि तिनीहरूसँग नोडहरूको संख्या छ भने, न्यूनतम मान दुवै नोडहरूको जस्तै हो। तर यदि तिनीहरूसँग नोडहरूको फरक संख्या थियो भने, हामीले सबैभन्दा नराम्रो अवस्थामा नोडहरूको न्यूनतम संख्या पार गर्नुपर्नेछ।

ठाउँ जटिलता

ओह), किनभने यदि हामी कम्पाइलर स्ट्याकका लागि आवश्यक स्थान विचार गर्दछौं। त्यसो भए आवश्यक ठाउँ कम्पाइलरले लिएको उस्तै हो।