C++ এ উল্টানো সাবট্রি

ধরুন আমাদের কাছে সোর্স এবং টার্গেট নামে দুটি বাইনারি ট্রি আছে; আমাদের পরীক্ষা করতে হবে যে উৎসের কিছু বিপরীত T আছে কি না যাতে এটি লক্ষ্যের একটি সাবট্রি। সুতরাং, এর মানে টার্গেটে একটি নোড রয়েছে যা তার সমস্ত বংশধর সহ T-এর মতো মান এবং কাঠামোতে অভিন্ন।

আমরা জানি যে একটি গাছকে অন্য গাছের বিপরীত বলা হয় যদি হয় −

• উভয় গাছই খালি

• এর বাম এবং ডান শিশু ঐচ্ছিকভাবে অদলবদল করা হয় এবং এর বাম এবং ডান উপবৃক্ষগুলি বিপরীত হয়৷

সুতরাং, যদি ইনপুট উৎসের মত হয়

লক্ষ্য

তাহলে আউটপুট হবে True

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

• একটি ফাংশন চেক () নির্ধারণ করুন, এটি node1, node2,

  নেবে

• যদি node1 এবং node2 উভয়ই শূন্য হয়, তাহলে −

  • প্রত্যাবর্তন সত্য

• যদি node1 বা node2 তাদের মধ্যে যেকোন একটি শূন্য হয়, তাহলে −

  • মিথ্যা ফেরত দিন

• যদি node1 এর val node2 এর val এর সমান না হয়, তাহলে −

  • মিথ্যা ফেরত দিন

• op1 :=চেক (নোড 1 এর বাম, নোড 2 এর বামে) এবং চেক (নোড1 এর ডান, নোড2 এর ডানদিকে)

• op2 :=চেক (নোড 1 এর ডানে, নোড 2 এর বামে) এবং চেক (নোড1 এর বামে, নোড2 এর ডানদিকে)

• op1 এবং op2-এর মধ্যে অন্তত একটি সত্য হলে সত্য ফেরত দিন

• একটি ফাংশন সল্ভ(), এটি সোর্স, টার্গেট,

  নেবে

• যদি উৎস এবং লক্ষ্য খালি হয়, তাহলে −

  • প্রত্যাবর্তন সত্য

• যদি উৎস বা লক্ষ্য তাদের মধ্যে যেকোনো একটি শূন্য হয়, তাহলে −

  • মিথ্যা ফেরত দিন

• op1 :=চেক (লক্ষ্য, উৎস)

• যদি op1 সত্য হয়, তাহলে −

  • প্রত্যাবর্তন সত্য

• সলভ (উৎস, টার্গেটের বাঁদিকে) বা সমাধান (উৎস, লক্ষ্যের ডানদিকে) সত্য হলে সত্য ফেরত দিন

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

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
class TreeNode {
   public:
   int val;
   TreeNode *left, *right;
   TreeNode(int data) {
      val = data;
      left = NULL;
      right = NULL;
   }
};
class Solution {
   public:
   bool check(TreeNode* node1, TreeNode* node2){
      if(!node1 && !node2)
      return true;
      if(!node1 || !node2)
      return false;
      if(node1->val != node2->val) {
         return false;
      }
      bool op1 = check(node1->left, node2->left) && check(node1->right, node2->right);
      bool op2 = check(node1->right, node2->left) && check(node1->left, node2->right);
      return op1 || op2;
   }
   bool solve(TreeNode* source, TreeNode* target) {
      if(!target && !source)
         return true;
      if(!target || !source)
         return false;
      bool op1 = check(target, source);
      if(op1)
         return true;
      return solve(source, target->left) || solve(source, target->right);
   }
};
main(){
   Solution ob;
   TreeNode *target = new TreeNode(6);
   target->left = new TreeNode(3);
   target->right = new TreeNode(1);
   target->right->left = new TreeNode(3);
   target->right->right = new TreeNode(2);
   target->right->right->left = new TreeNode(4);
   TreeNode *source = new TreeNode(1);
   source->left = new TreeNode(2);
   source->right = new TreeNode(3);
   source->left->right = new TreeNode(4);
   cout << (ob.solve(source, target));
}

ইনপুট

TreeNode *target = new TreeNode(6);
target->left = new TreeNode(3);
target->right = new TreeNode(1);
target->right->left = new TreeNode(3);
target->right->right = new TreeNode(2);
target->right->right->left = new TreeNode(4);
TreeNode *source = new TreeNode(1);
source->left = new TreeNode(2);
source->right = new TreeNode(3);
source->left->right = new TreeNode(4);

আউটপুট

1