ধরা যাক একটি বাইনারি ট্রি আছে। আমরা ট্রিটি ফ্লিপ করব। ফ্লিপ বলতে বুঝায়: যেকোনো নোড বেছে নিয়ে তার বাম ও ডান চাইল্ড সাবট্রি स्व্যাপ করা। এখন একটি বাইনারি ট্রি X, অন্য বাইনারি ট্রি Y-এর সাথে ফ্লিপ সমতুল্য (flip equivalent) হবে যদি এবং কেবল যদি X-কে কিছু ফ্লিপ অপারেশন করলে Y তৈরি করা যায়। দুটি ট্রির রুট নোড root1 এবং root2 দেওয়া থাকলে আমরা যাচাই করব সেগুলো ফ্লিপ সমতুল্য কিনা। যদি ট্রিগুলো নিচের মতো হয় −
তবে আউটপুট হবে true, যদি আমরা ১, ৩ এবং ৫ মান वाले নোডগুলো ফ্লিপ করি।
সমাধানের ধাপগুলো −
solve() নামে একটি রিকারসিভ ফাংশন সংজ্ঞা করব, যা দুটি ট্রি t1 এবং t2 নিবে।
যদি root1 এবং root2 উভয়ই null হয়, তবে true রিটার্ন করব
অন্যথায় যদি root1 null হয় বা root2 null হয়, তবে false রিটার্ন করব
অন্যথায় যদি (t1 এবং t2 উভয়েরই বাম সাবট্রি নেই) অথবা (t1 এবং t2 উভয়েরই বাম সাবট্রি আছে এবং সেগুলোর মান সমান), তবে
রিটার্ন solve(রুট1-এর বাম, রুট2-এর বাম) এবং solve(রুট1-এর ডান, রুট2-এর ডান)
অন্যথায়
রিটার্ন solve(রুট1-এর বাম, রুট2-এর ডান) এবং solve(রুট1-এর ডান, রুট2-এর বাম)
নিচের ইমপ্লিমেন্টেশন দেখুন −
উদাহরণ
#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
