ধরুন আমাদের একটি বাইনারি গাছ আছে। আমরা বাইনারি গাছ উল্টাতে হবে. ফ্লিপ নির্দেশ করে:যেকোনো নোড বেছে নিন এবং বাম ও ডানের চাইল্ড সাবট্রি অদলবদল করুন। এখন একটি বাইনারি ট্রি X একটি বাইনারি ট্রি Y-এর সমতুল্য যদি এবং শুধুমাত্র যদি আমরা কিছু সংখ্যক ফ্লিপ অপারেশনের পরে X থেকে Y তৈরি করতে পারি। আমাদের একটি পদ্ধতি লিখতে হবে যা নির্ধারণ করে যে দুটি বাইনারি গাছ ফ্লিপ সমতুল্য কিনা। গাছ রুট নোড root1 এবং root2 দ্বারা দেওয়া হয়. তাই যদি গাছ হয় -
তারপর আউটপুট সত্য হবে, যদি আমরা 1, 3 এবং 5 মান সহ নোডগুলি ফ্লিপ করি।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি পুনরাবৃত্ত ফাংশন সংজ্ঞায়িত করুন সমাধান(), এটি t1 এবং t2 দুটি গাছ লাগবে।
-
root1 এবং root2 যদি শূন্য হয়, তাহলে true রিটার্ন করুন
-
অন্যথায় যখন root1 নাল বা root2 শূন্য হয়, তখন মিথ্যা ফেরত দিন
-
অন্যথায় যখন (t1 এবং t2 উভয়েরই বাম সাবট্রি নেই) বা (t1 এবং t2 উভয়েরই বাম সাবট্রি থাকে এবং এই দুটি নোডের বাম সাবট্রির মান একই থাকে), তখন
-
সমাধান (root1 এর বামে, root2 এর বামে) এবং সমাধান (root1 এর ডানে, root2 এর ডানদিকে)
-
-
অন্যথায়
-
সমাধান (root1 এর বামে, root2 এর ডানে) এবং সমাধান (root1 এর ডানে, root2 এর বামে)
-
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#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 flipEquiv(TreeNode* root1, TreeNode* root2) {
if(!root1 && !root2)return true;
else if(!root1 || !root2)return false;
else if(root1->val != root2->val) return false;
else if((!root1->left && !root2->left) || (root1->left && root2->left && root1->left->val == root2- >left->val)){
return flipEquiv(root1->left, root2->left) && flipEquiv(root1->right, root2->right);
}else{
return flipEquiv(root1->left, root2->right) && flipEquiv(root1->right, root2->left);
}
}
};
main(){
vector<int> v = {1,2,3,4,5,6,NULL,NULL,NULL,7,8};
TreeNode *r1 = make_tree(v);
vector<int> v1 = {1,3,2,NULL,6,4,5,NULL,NULL,NULL,NULL,NULL,NULL,8,7};
TreeNode *r2 = make_tree(v);
Solution ob;
cout << (ob.flipEquiv(r1, r2));
} ইনপুট
[1,2,3,4,5,6,null,null,null,7,8] [1,3,2,null,6,4,5,null,null,null,null,8,7]
আউটপুট
1
