ਇਹ ਨਿਰਧਾਰਤ ਕਰਨ ਲਈ ਕੋਡ ਲਿਖੋ ਕਿ ਕੀ ਦੋ ਰੁੱਖ ਇਕੋ ਜਿਹੇ ਹਨ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਸੌਖੀ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਐਮਾਜ਼ਾਨ ਤੱਥ ਕੱਟੜਪੰਥੀ GE ਹੈਲਥਕੇਅਰ Microsoft ਦੇ ਪੇਪਾਲ
ਬਾਈਨਰੀ ਟਰੀ ਟ੍ਰੀ

ਸਮੱਸਿਆ ਦਾ ਪਤਾ ਲਗਾਉਣ ਲਈ ਕੋਡ ਲਿਖੋ ਜੇ ਦੋ ਰੁੱਖ ਇੱਕੋ ਜਿਹੇ ਹਨ "ਦੱਸਦਾ ਹੈ ਕਿ ਤੁਹਾਨੂੰ ਦੋ ਬਾਈਨਰੀ ਰੁੱਖ ਦਿੱਤੇ ਗਏ ਹਨ. ਪਤਾ ਲਗਾਓ ਕਿ ਉਹ ਇਕੋ ਜਿਹੇ ਹਨ ਜਾਂ ਨਹੀਂ? ਇੱਥੇ, ਇਕੋ ਜਿਹੇ ਰੁੱਖ ਦਾ ਅਰਥ ਹੈ ਕਿ ਦੋਵੇਂ ਬਾਈਨਰੀ ਰੁੱਖ ਇਕੋ ਜਿਹੇ ਨੋਡਾਂ ਦੇ ਇਕੋ ਜਿਹੇ ਪ੍ਰਬੰਧ ਨਾਲ ਇਕੋ ਇਕ ਨੋਡ ਮੁੱਲ ਹਨ.

ਉਦਾਹਰਨ

ਇਹ ਨਿਰਧਾਰਤ ਕਰਨ ਲਈ ਕੋਡ ਲਿਖੋ ਕਿ ਕੀ ਦੋ ਰੁੱਖ ਇਕੋ ਜਿਹੇ ਹਨ

Both trees are identical.

ਕਥਾ

ਦੋਵੇਂ ਰੁੱਖ ਇਕੋ ਜਿਹੇ ਮੁੱਲ ਵਾਲੇ ਨੋਡਜ਼ ਹਨ. ਨਾਲ ਹੀ, ਉਨ੍ਹਾਂ ਦਾ ਇਕੋ ਜਿਹਾ ਨੋਡ ਪ੍ਰਬੰਧ ਹੈ. ਇਸ ਤਰ੍ਹਾਂ ਦੋਵੇਂ ਰੁੱਖ ਇਕੋ ਜਿਹੇ ਹਨ.

ਪਹੁੰਚ

A ਬਾਈਨਰੀ ਟਰੀ ਹਰੇਕ ਨੋਡ ਲਈ ਸਿਰਫ ਦੋ ਬੱਚੇ ਹਨ. ਹੁਣ ਸਾਨੂੰ ਬਾਈਨਰੀ ਰੁੱਖ ਦੀਆਂ ਦੋ ਜੜ੍ਹਾਂ ਦਿੱਤੀਆਂ ਗਈਆਂ ਹਨ, ਅਤੇ ਸਾਨੂੰ ਇਹ ਵੇਖਣ ਦੀ ਜ਼ਰੂਰਤ ਹੈ ਕਿ ਕੀ ਦੋਵੇਂ ਰੁੱਖ ਇਕੋ ਜਿਹੇ ਹਨ ਜਾਂ ਨਹੀਂ. ਅਸੀਂ ਕਹਿੰਦੇ ਹਾਂ ਕਿ ਦੋ ਰੁੱਖ ਇਕੋ ਜਿਹੇ ਹਨ ਜੇ ਉਨ੍ਹਾਂ ਵਿਚ ਨੋਡਾਂ ਦਾ ਇਕੋ ਜਿਹਾ ਪ੍ਰਬੰਧ ਹੈ. ਉਸੇ ਪ੍ਰਬੰਧ ਦੁਆਰਾ, ਸਾਡਾ ਮਤਲਬ ਹੈ ਕਿ ਜੇ ਕੁਝ ਨੋਡ ਕੁਝ ਨੋਡ ਦੇ ਖੱਬੇ ਦਿਸ਼ਾ ਵਿੱਚ ਹੈ. ਉਨ੍ਹਾਂ ਨੂੰ ਦੂਜੇ ਦਰੱਖਤ ਵਿਚ ਇਕੋ ਜਿਹੇ ਪ੍ਰਬੰਧ ਵਿਚ ਹੋਣ ਦੀ ਜ਼ਰੂਰਤ ਹੈ. ਜੇ ਦੋਵਾਂ ਰੁੱਖਾਂ ਦਾ ਇਕੋ ਜਿਹਾ ਪ੍ਰਬੰਧ ਹੈ, ਤਾਂ ਉਹਨਾਂ ਨੂੰ ਦੋਵਾਂ ਰੁੱਖਾਂ ਵਿਚ ਹਰੇਕ ਸੰਬੰਧਿਤ ਨੋਡਾਂ ਲਈ ਇਕੋ ਮੁੱਲ ਦੀ ਜ਼ਰੂਰਤ ਹੈ.

ਹੁਣ ਅਸੀਂ ਜਾਣਦੇ ਹਾਂ ਕਿ ਕਿਹੜੇ ਰੁੱਖ ਇਕੋ ਜਿਹੇ ਹੁੰਦੇ ਹਨ. ਇਸ ਲਈ ਹੁਣ ਅਸੀਂ ਇਹ ਵੇਖਣ ਦੀ ਕੋਸ਼ਿਸ਼ ਕਰਾਂਗੇ ਕਿ ਦਿੱਤੇ ਗਏ ਦਰੱਖਤ ਇਕੋ ਜਿਹੇ ਹਨ ਜਾਂ ਨਹੀਂ. ਵਿਧੀ ਸਰਲ ਹੈ. ਸਾਨੂੰ ਦਰੱਖਤ ਪਾਰ ਕਰਨ ਦੀ ਜ਼ਰੂਰਤ ਹੈ. ਰੁੱਖ ਨੂੰ ਟ੍ਰਾਂਸ ਕਰਦੇ ਸਮੇਂ, ਅਸੀਂ ਜਾਂਚ ਕਰਦੇ ਰਹਿੰਦੇ ਹਾਂ ਕਿ ਕੀ ਪਹਿਲੇ ਦਰੱਖਤ ਦਾ ਮੌਜੂਦਾ ਨੋਡ ਦੂਜੇ ਦਰੱਖਤ ਵਰਗਾ ਹੈ ਜਾਂ ਨਹੀਂ ਜੇ ਉਹ ਵੱਖਰੇ ਹਨ, ਤਾਂ ਉਹ ਇਕੋ ਜਿਹੇ ਨਹੀਂ ਹਨ. ਭਾਵੇਂ ਉਨ੍ਹਾਂ ਦੇ ਕੁਝ ਵੱਖਰੇ ਪ੍ਰਬੰਧ ਹੋਣ. ਜਾਂ ਜੇ ਇਕ ਦਰੱਖਤ ਦੇ ਦੂਸਰੇ ਦਰਜੇ ਦੇ ਮੁਕਾਬਲੇ ਵਾਧੂ ਨੋਡ ਸਨ. ਫਿਰ ਵੀ, ਅਸੀਂ ਇਸ ਨੂੰ ਉਸੇ ਤਰੀਕੇ ਨਾਲ ਸਮਝ ਸਕਦੇ ਹਾਂ. ਕਿਉਂਕਿ ਜੇ ਕਿਸੇ ਰੁੱਖ ਕੋਲ ਇੱਕ ਵਾਧੂ ਨੋਡ ਹੁੰਦਾ, ਤਾਂ ਦੂਜੇ ਦਰੱਖਤ ਦਾ ਉਸ ਸਥਿਤੀ ਤੇ ਪੂਰਾ ਮੁੱਲ ਹੋਵੇਗਾ. ਇਸ ਦੇ ਨਤੀਜੇ ਵਜੋਂ ਗੈਰ-ਸਮਾਨ ਰੁੱਖ ਹੋਣਗੇ. ਇਸ ਲਈ ਅਸੀਂ ਇਹ ਨਿਰਧਾਰਤ ਕਰਨ ਲਈ ਕੋਡ ਲਿਖਦੇ ਹਾਂ ਕਿ ਕੀ ਦੋ ਰੁੱਖ ਇਕੋ ਜਿਹੇ ਹਨ.

ਕੋਡ

ਸੀ ++ ਕੋਡ ਨੂੰ ਨਿਰਧਾਰਤ ਕਰਨ ਲਈ ਕਿ ਕੀ ਦੋ ਦਰੱਖਤ ਇਕੋ ਜਿਹੇ ਹਨ

#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 ਦੋਵਾਂ ਰੁੱਖਾਂ ਵਿਚ ਨੋਡਾਂ ਦੀ ਘੱਟੋ ਘੱਟ ਗਿਣਤੀ ਦਰਸਾਉਂਦਾ ਹੈ. ਕਿਉਕਿ ਅਸੀਂ ਰੁੱਖਾਂ ਵਿਚ ਗੰ .ਾਂ ਪਾਰ ਕਰ ਚੁੱਕੇ ਹਾਂ. ਜੇ ਉਨ੍ਹਾਂ ਕੋਲ ਇਕੋ ਜਿਹੇ ਨੋਡ ਸਨ, ਤਾਂ ਘੱਟੋ ਘੱਟ ਮੁੱਲ ਦੋਵੇਂ ਨੋਡਾਂ ਦੇ ਸਮਾਨ ਹੈ. ਪਰ ਜੇ ਉਨ੍ਹਾਂ ਕੋਲ ਵੱਖੋ ਵੱਖਰੇ ਨੋਡ ਸਨ, ਤਾਂ ਸਾਨੂੰ ਸਭ ਤੋਂ ਭੈੜੀ ਸਥਿਤੀ ਵਿਚ ਨੋਡਾਂ ਦੀ ਘੱਟੋ ਘੱਟ ਗਿਣਤੀ ਨੂੰ ਪਾਰ ਕਰਨਾ ਪਏਗਾ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਓ (ਐਚ), ਕਿਉਂਕਿ ਜੇ ਅਸੀਂ ਕੰਪਾਈਲਰ ਸਟੈਕ ਲਈ ਲੋੜੀਂਦੀ ਜਗ੍ਹਾ 'ਤੇ ਵਿਚਾਰ ਕਰਦੇ ਹਾਂ. ਫਿਰ ਲੋੜੀਂਦੀ ਜਗ੍ਹਾ ਕੰਪਾਈਲਰ ਦੁਆਰਾ ਲਈ ਗਈ ਇਕੋ ਜਿਹੀ ਹੈ.