ሁለት ዛፎች ተመሳሳይ ከሆኑ ለመለየት ኮድ ይጻፉ  


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን ፋርስት አፍቃሪዎች GE የጤና የ Microsoft የ 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

ውስብስብነት ትንተና  

የጊዜ ውስብስብነት

ኦ (ኤን) ፣ N በሁለቱም ዛፎች ውስጥ አነስተኛውን የአንጓዎች ቁጥር የሚያመለክት። በዛፎቹ ውስጥ ያሉትን አንጓዎች ስለ ተሻገርን ፡፡ ተመሳሳይ ቁጥር ያላቸው ኖዶች ነበሯቸው ከሆነ አነስተኛው እሴት ከሁለቱም አንጓዎች ጋር ተመሳሳይ ነው ፡፡ ግን የተለያየ ቁጥር ያላቸው ኖዶች ቢኖሯቸው በጣም በከፋ ሁኔታ አነስተኛውን የአንጓዎች ቁጥር ማለፍ አለብን ፡፡

ተመልከት
ዱካ ድምር

የቦታ ውስብስብነት

ኦ (ኤች) ፣ ምክንያቱም ለአቀናባሪው ቁልል የሚያስፈልገውን ቦታ ከግምት ካስገባን ፡፡ ከዚያ የሚፈለገው ቦታ በአቀናባሪው ከተወሰደው ጋር ተመሳሳይ ነው።