C++ এ একই গাছ

ধরুন আমাদের দুটি বাইনারি গাছ আছে; তারা একই কিনা তা পরীক্ষা করার জন্য আমাদের একটি ফাংশন সংজ্ঞায়িত করতে হবে। আমরা জানি যে বাইনারি গাছ একই বলে বিবেচিত হয় যখন সেগুলি গঠনগতভাবে অভিন্ন হয় এবং নোডগুলির মান একই থাকে৷

সুতরাং, ইনপুট যদি [1,2,3],[1,2,3] এর মত হয়, তাহলে আউটপুট হবে True

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

isSameTree নামক একটি ফাংশন সংজ্ঞায়িত করুন, এটি দুটি ট্রি নোড p এবং q
নেবে
যদি p NULL এর মত হয় এবং q NULL এর মত হয়, তাহলে −
- প্রত্যাবর্তন সত্য
যদি p NULL এর মত হয় বা q NULL এর মত হয়, তাহলে −
- ফেরত মিথ্যা
যদি p এর val p এর val এর সমান হয় এবং isSameTree(p এর বাম, q এর বাম) সত্য হয় এবং isSameTree(p এর ডান, q এর ডান) সত্য হয়, তাহলে
- প্রত্যাবর্তন সত্য
ফেরত মিথ্যা

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
   public:
      int val;
      TreeNode *left, *right;
      TreeNode(int data){
         val = data;
         left = NULL;
         right = NULL;
      }
};
void insert(TreeNode **root, int val){
   queue<TreeNode*> q;
   q.push(*root);
   while(q.size()){
      TreeNode *temp = q.front();
      q.pop();
      if(!temp->left){
         if(val != NULL)
            temp->left = new TreeNode(val);
         else
            temp->left = new TreeNode(0);
         return;
      }
      else{
         q.push(temp->left);
      }
      if(!temp->right){
         if(val != NULL)
            temp->right = new TreeNode(val);
         else
            temp->right = new TreeNode(0);
         return;
      }
      else{
         q.push(temp->right);
      }
   }
}
TreeNode *make_tree(vector<int> v){
   TreeNode *root = new TreeNode(v[0]);
   for(int i = 1; i<v.size(); i++){
      insert(&root, v[i]);
   }
   return root;
}
class Solution {
public:
   bool isSameTree(TreeNode *p, TreeNode* q){
      if (p == NULL && q == NULL)
         return true;
      if (p == NULL || q == NULL)
         return false;
      if (p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right))
         return true;
      return false;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,3}, v1 = {1,2,3};
   TreeNode *root1 = make_tree(v);
   TreeNode *root2 = make_tree(v1);
   cout << (ob.isSameTree(root1, root2));
}

ইনপুট

{1,2,3}, {1,2,3}