இரண்டு மரங்கள் ஒரே மாதிரியானவை என்பதை தீர்மானிக்க குறியீடு எழுதவும்  


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அமேசான் உண்மை வெறியர்கள் 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

சிக்கலான பகுப்பாய்வு  

நேர சிக்கலானது

ஓ (என்), இரண்டு மரங்களிலும் குறைந்தபட்ச முனைகளின் எண்ணிக்கையை N குறிக்கிறது. நாங்கள் மரங்களில் உள்ள முனைகளை கடந்து சென்றதால். அவை ஒரே எண்ணிக்கையிலான முனைகளைக் கொண்டிருந்தால், குறைந்தபட்ச மதிப்பு இரு முனைகளுக்கும் சமம். ஆனால் அவை வேறுபட்ட எண்ணிக்கையிலான முனைகளைக் கொண்டிருந்தால், மிக மோசமான நிலையில் குறைந்தபட்ச எண்ணிக்கையிலான முனைகளைக் கடந்து செல்ல வேண்டும்.

மேலும் காண்க
பாதை தொகை

விண்வெளி சிக்கலானது

ஓ (எச்), ஏனெனில் கம்பைலர் ஸ்டேக்கிற்கு தேவையான இடத்தை நாங்கள் கருத்தில் கொண்டால். பின்னர் தேவையான இடம் கம்பைலர் எடுத்த இடத்திற்கு சமம்.