დაწერეთ კოდი, რათა დადგინდეს, ორი ხე იდენტურია


Რთული ტური Easy
ხშირად ეკითხებიან Amazon ფაქტები ფანატიკა GE Healthcare 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

სირთულის ანალიზი

დროის სირთულე

O (N), სადაც N აღნიშნავს კვანძების მინიმალურ რაოდენობას ორივე ხეში. მას შემდეგ, რაც ჩვენ გადავკვეთეთ კვანძები ხეებში. თუ მათ ჰქონდათ იგივე რაოდენობის კვანძები, მაშინ მინიმალური მნიშვნელობა იგივეა, რაც ორივე კვანძი. მაგრამ თუ მათ სხვადასხვა რაოდენობის კვანძი ჰქონდათ, უარეს შემთხვევაში უნდა გადავკვეთოთ კვანძების მინიმალური რაოდენობა.

სივრცის სირთულე

O (H), რადგან თუ გავითვალისწინებთ შემდგენლის დასტისთვის საჭირო ადგილს. მაშინ საჭირო სივრცე იგივეა, რაც კომპილატორის მიერ აღებული.