രണ്ട് മരങ്ങൾ സമാനമാണോ എന്ന് നിർണ്ണയിക്കാൻ കോഡ് എഴുതുക


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ആമസോൺ ഫാക്റ്റ്സെറ്റ് ഫനാറ്റിക്സ് GE ഹെൽത്ത്കെയർ മൈക്രോസോഫ്റ്റ് പേപാൽ
ബൈനറി ട്രീ വൃക്ഷം

“രണ്ട് മരങ്ങൾ ഒരേപോലെയാണോ എന്ന് നിർണ്ണയിക്കാൻ കോഡ് എഴുതുക” എന്ന പ്രശ്നം നിങ്ങൾക്ക് രണ്ട് ബൈനറി ട്രീകൾ നൽകിയിട്ടുണ്ടെന്ന് പറയുന്നു. അവ സമാനമാണോ അല്ലയോ എന്ന് കണ്ടെത്തണോ? ഇവിടെ, സമാനമായ ട്രീ എന്നാൽ രണ്ട് ബൈനറി ട്രീകൾക്കും ഒരേ നോഡ് മൂല്യമുള്ള നോഡ് മൂല്യമുണ്ടെന്ന് അർത്ഥമാക്കുന്നു.

ഉദാഹരണം

രണ്ട് മരങ്ങൾ സമാനമാണോ എന്ന് നിർണ്ണയിക്കാൻ കോഡ് എഴുതുക

Both trees are identical.

വിശദീകരണം

രണ്ട് മരങ്ങൾക്കും ഒരേ മൂല്യമുള്ള നോഡുകളുണ്ട്. കൂടാതെ, അവർക്ക് ഒരേ നോഡ് ക്രമീകരണം ഉണ്ട്. അങ്ങനെ രണ്ട് വൃക്ഷങ്ങളും സമാനമാണ്.

സമീപനം

A ബൈനറി ട്രീ ഓരോ നോഡിനും രണ്ട് കുട്ടികൾ മാത്രമേയുള്ളൂ. ഇപ്പോൾ നമുക്ക് ബൈനറി ട്രീയുടെ രണ്ട് വേരുകൾ നൽകിയിട്ടുണ്ട്, രണ്ട് വൃക്ഷങ്ങളും സമാനമാണോ എന്ന് പരിശോധിക്കേണ്ടതുണ്ട്. രണ്ട് വൃക്ഷങ്ങൾക്ക് നോഡുകളുടെ സമാന ക്രമീകരണം ഉണ്ടെങ്കിൽ അവ സമാനമാണെന്ന് ഞങ്ങൾ വിളിക്കുന്നു. അതേ ക്രമീകരണത്തിലൂടെ, ചില നോഡ് ചില നോഡിന്റെ ഇടത് ദിശയിലാണെങ്കിൽ ഞങ്ങൾ അർത്ഥമാക്കുന്നു. മറ്റ് വൃക്ഷത്തിലും അവർ ഒരേ ക്രമീകരണത്തിൽ ആയിരിക്കണം. രണ്ട് വൃക്ഷങ്ങൾക്കും ഒരേ ക്രമീകരണം ഉണ്ടെങ്കിൽ, രണ്ട് വൃക്ഷങ്ങളിലെയും അനുബന്ധ നോഡുകൾക്ക് ഒരേ മൂല്യം ആവശ്യമാണ്.

മരങ്ങളെ സമാനമെന്ന് വിളിക്കുന്നതിനെ ഇപ്പോൾ നമുക്കറിയാം. തന്നിരിക്കുന്ന രണ്ട് വൃക്ഷങ്ങൾ സമാനമാണോയെന്ന് പരിശോധിക്കാനുള്ള ഒരു മാർഗ്ഗം കണ്ടെത്താൻ ഞങ്ങൾ ശ്രമിക്കും. രീതി ലളിതമാണ്. നാം മരങ്ങൾ സഞ്ചരിക്കേണ്ടതുണ്ട്. ട്രീയിലൂടെ സഞ്ചരിക്കുമ്പോൾ, ആദ്യത്തെ ട്രീയുടെ നിലവിലെ നോഡ് രണ്ടാമത്തെ ട്രീയുടെ തുല്യമാണോ എന്ന് ഞങ്ങൾ പരിശോധിച്ചുകൊണ്ടിരിക്കും. അവ വ്യത്യാസമുണ്ടെങ്കിൽ, അവ സമാനമല്ല. അവർക്ക് ചില വ്യത്യസ്ത ക്രമീകരണങ്ങളുണ്ടെങ്കിലും. അല്ലെങ്കിൽ വൃക്ഷങ്ങളിലൊന്നിൽ മറ്റൊന്നിനെ അപേക്ഷിച്ച് അധിക നോഡുകൾ ഉണ്ടെങ്കിൽ. അതേ രീതിയിലൂടെയും നമുക്ക് അത് മനസിലാക്കാൻ കഴിയും. കാരണം ചില വൃക്ഷങ്ങൾക്ക് ഒരു അധിക നോഡ് ഉണ്ടെങ്കിൽ, മറ്റ് വൃക്ഷത്തിന് ആ സ്ഥാനത്ത് 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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (N), ഇവിടെ രണ്ട് വൃക്ഷങ്ങളിലെയും ഏറ്റവും കുറഞ്ഞ നോഡുകളുടെ എണ്ണം N സൂചിപ്പിക്കുന്നു. ഞങ്ങൾ മരങ്ങളിലെ നോഡുകളിലൂടെ സഞ്ചരിച്ചതിനാൽ. അവയ്‌ക്ക് ഒരേ എണ്ണം നോഡുകളുണ്ടെങ്കിൽ, ഏറ്റവും കുറഞ്ഞ മൂല്യം രണ്ട് നോഡുകളുടെയും തുല്യമാണ്. പക്ഷേ അവയ്‌ക്ക് വ്യത്യസ്‌ത എണ്ണം നോഡുകളുണ്ടെങ്കിൽ‌, ഏറ്റവും മോശം അവസ്ഥയിൽ‌ ഞങ്ങൾ‌ ഏറ്റവും കുറഞ്ഞ നോഡുകളിലൂടെ സഞ്ചരിക്കണം.

ബഹിരാകാശ സങ്കീർണ്ണത

O (H), കാരണം കംപൈലർ സ്റ്റാക്കിന് ആവശ്യമായ ഇടം ഞങ്ങൾ പരിഗണിക്കുകയാണെങ്കിൽ. അപ്പോൾ ആവശ്യമായ ഇടം കംപൈലർ എടുത്തതിന് തുല്യമാണ്.