બે વૃક્ષો સરખા છે કે કેમ તે નક્કી કરવા માટે કોડ લખો


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એમેઝોન ફેક્ટસેટ કટ્ટરતા જીઇ હેલ્થકેર માઈક્રોસોફ્ટ પેપાલ
દ્વિસંગી વૃક્ષ વૃક્ષ

સમસ્યા "બે વૃક્ષો સમાન છે તે નક્કી કરવા માટે કોડ લખો" કહે છે કે તમને બે બાઈનરી ટ્રી આપવામાં આવે છે. તેઓ સરખા છે કે નહીં તે શોધી કા ?ો? અહીં, સરખા વૃક્ષનો અર્થ એ છે કે બંને બાઈનરી ઝાડ ગાંઠોની સમાન ગોઠવણી સાથે સમાન નોડ મૂલ્ય ધરાવે છે.

ઉદાહરણ

બે વૃક્ષો સરખા છે કે કેમ તે નક્કી કરવા માટે કોડ લખો

Both trees are identical.

સમજૂતી

બંને ઝાડ સમાન મૂલ્યવાળા ગાંઠો ધરાવે છે. ઉપરાંત, તેમની સમાન નોડ વ્યવસ્થા છે. આમ બંને વૃક્ષો સરખા છે.

અભિગમ

A દ્વિસંગી વૃક્ષ દરેક ગાંઠો માટે ફક્ત બે બાળકો છે. હવે અમને દ્વિસંગી ઝાડની બે મૂળ આપવામાં આવી છે, અને આપણે તપાસ કરવાની જરૂર છે કે બંને ઝાડ સરખા છે કે નહીં. અમે ક treesલ કરીએ છીએ કે બે વૃક્ષો સરખા છે જો તેમની પાસે ગાંઠોની સમાન વ્યવસ્થા હોય. સમાન ગોઠવણી દ્વારા, અમારું અર્થ એ છે કે જો કેટલાક નોડ કેટલાક નોડની ડાબી દિશામાં હોય તો. તેમને અન્ય ઝાડમાં સમાન ગોઠવણમાં રહેવાની જરૂર છે. જો બંને ઝાડની સમાન વ્યવસ્થા હોય, તો તે બંને ઝાડમાંના દરેક અનુરૂપ ગાંઠો માટે સમાન મૂલ્ય હોવું જરૂરી છે.

હવે આપણે જાણીએ છીએ કે કયા વૃક્ષોને સરખા કહેવામાં આવે છે. તેથી હવે આપણે આપેલ બે વૃક્ષો સરખા છે કે નહીં તે તપાસવાની રીત કા figureવાનો પ્રયત્ન કરીશું. પદ્ધતિ સરળ છે. આપણે ઝાડ પાર કરવાની જરૂર છે. ઝાડને ટ્રversવર્સ કરતી વખતે, અમે તપાસ ચાલુ રાખીએ છીએ કે પહેલા ઝાડનું વર્તમાન નોડ બીજા ઝાડ જેવું જ છે કે નહીં. જો તેઓ તફાવત કરે છે, તો પછી તે સમાન નથી. ભલે તેમની કેટલીક અલગ વ્યવસ્થા હોય. અથવા જો બીજા એકની તુલનામાં એક ઝાડ પાસે વધારાના ગાંઠો છે. તો પછી, આપણે તે જ પદ્ધતિ દ્વારા આકૃતિ કરી શકીએ છીએ. કારણ કે જો કેટલાક ઝાડનું વધારાનું નોડ હોય, તો બીજા ઝાડની તે સ્થિતિ પર નલ મૂલ્ય હશે. આના પરિણામે બિન-સમાન વૃક્ષો બનશે. તેથી તે છે કે આપણે કેવી રીતે બે ઝાડ સરખા છે કે કેમ તે નિર્ધારિત કરવા માટે કોડ લખો

કોડ

સી ++ કોડ નક્કી કરવા માટે જો બે વૃક્ષો સમાન હોય

#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

જટિલતા વિશ્લેષણ

સમયની જટિલતા

ઓ (એન), જ્યાં એન બંને ઝાડમાં ઓછામાં ઓછી સંખ્યાની ગાંઠો દર્શાવે છે. અમે ઝાડમાં ગાંઠો વટાવી દીધા છે. જો તેમની પાસે સમાન ગાંઠો હોય, તો ન્યૂનતમ મૂલ્ય બંને નોડ્સ જેટલું જ છે. પરંતુ જો તેમની પાસે ગાંઠોની સંખ્યા જુદી હોય, તો આપણે સૌથી ખરાબ કિસ્સામાં નોડ્સની ન્યૂનતમ સંખ્યાને વટાવીશું.

અવકાશ જટિલતા

ઓ (એચ), કારણ કે જો આપણે કમ્પાઇલર સ્ટેક માટે જરૂરી જગ્યાને ધ્યાનમાં લઈએ. પછી જરૂરી જગ્યા તે જ છે જે કમ્પાઇલર દ્વારા લેવાયેલી છે.