اكتب رمزًا لتحديد ما إذا كانت شجرتان متطابقتين


مستوى الصعوبة سهل
كثيرا ما يطلب في أمازون مجموعة الحقائق المتعصبون جنرال إلكتريك للرعاية الصحية Microsoft Paypal
شجرة ثنائية شجرة

تشير مشكلة "كتابة رمز لتحديد ما إذا كانت شجرتان متطابقتان" إلى أنه تم منحك شجرتين ثنائيتين. اكتشف ما إذا كانت متطابقة أم لا؟ هنا ، تعني الشجرة المتطابقة أن كلا الشجرتين الثنائيتين لهما نفس قيمة العقدة بنفس ترتيب العقد.

مثال

اكتب رمزًا لتحديد ما إذا كانت شجرتان متطابقتين

Both trees are identical.

تفسير

كلا الشجرتين لهما العقد بنفس القيمة. أيضا ، لديهم نفس ترتيب العقدة. وبالتالي كلا الشجرتين متطابقتان.

الرسالة

A شجرة ثنائية لديه طفلان فقط لكل عقدة. لدينا الآن جذرين من الشجرة الثنائية ، وعلينا التحقق مما إذا كانت كلتا الشجرتين متطابقتين. نسمي شجرتين متطابقتين إذا كان لهما نفس ترتيب العقد. بنفس الترتيب ، فإننا نعني أنه إذا كانت بعض العقد في الاتجاه الأيسر لبعض العقد. يجب أن يكونوا في نفس الترتيب في الشجرة الأخرى. إذا كان لكل من الشجرتين نفس الترتيب ، فيجب أن يكون لهما نفس القيمة لكل من العقد المقابلة في كلتا الشجرتين.

الآن نحن نعرف ما تسمى الأشجار متطابقة. سنحاول الآن اكتشاف طريقة للتحقق مما إذا كانت شجرتان متطابقتان. الطريقة بسيطة. نحن بحاجة لاجتياز الأشجار. أثناء عبور الشجرة ، نستمر في التحقق مما إذا كانت العقدة الحالية للشجرة الأولى هي نفس عقدة الشجرة الثانية. إذا اختلفوا ، فليسوا متطابقين. حتى لو كان لديهم بعض الترتيبات المختلفة. أو إذا كانت إحدى الشجرتين تحتوي على عقد إضافية مقارنة بالعقد الأخرى. ثم أيضًا ، يمكننا معرفة ذلك بنفس الطريقة. لأنه إذا كانت هناك شجرة تحتوي على عقدة إضافية ، فستكون للشجرة الأخرى قيمة فارغة في هذا الموضع. سيؤدي هذا إلى أشجار غير متطابقة. هذه هي الطريقة التي نكتب بها الكود لتحديد ما إذا كانت شجرتان متطابقتين.

رمز

كود 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 إلى الحد الأدنى لعدد العقد في كلتا الشجرتين. منذ أن اجتزنا العقد في الأشجار. إذا كان لديهم نفس عدد العقد ، فإن الحد الأدنى للقيمة هو نفس قيمة كلتا العقدتين. ولكن إذا كان لديهم عدد مختلف من العقد ، فيجب علينا اجتياز الحد الأدنى لعدد العقد في أسوأ الحالات.

تعقيد الفضاء

أوه)، لأنه إذا أخذنا في الاعتبار المساحة المطلوبة لمكدس المترجم. ثم تكون المساحة المطلوبة هي نفسها التي يشغلها المترجم.