Екі ағаштың бірдей екенін анықтау үшін код жазыңыз


Күрделілік дәрежесі оңай
Жиі кіреді Amazon Factset Фанатика 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

Екі ағаштың бірдей екенін анықтайтын Java коды

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), өйткені компилятор стегі үшін қажет орынды қарастырсақ. Сонда қажет орын компилятор қабылдағанмен бірдей болады.