मान लीजिए कि हमारे पास एक बाइनरी ट्री है। हमें बाइनरी ट्री को पलटना है। फ्लिप इंगित करता है:कोई भी नोड चुनें, और बाएँ और दाएँ चाइल्ड सबट्री को स्वैप करें। अब एक बाइनरी ट्री एक्स एक बाइनरी ट्री वाई के बराबर फ्लिप है यदि और केवल अगर हम कुछ फ्लिप ऑपरेशन के बाद एक्स से वाई बना सकते हैं। हमें एक विधि लिखनी है जो यह निर्धारित करती है कि क्या दो बाइनरी ट्री फ्लिप समतुल्य हैं। पेड़ रूट नोड्स रूट 1 और रूट 2 द्वारा दिए गए हैं। तो अगर पेड़ हैं -
तब आउटपुट सही होगा, अगर हम 1, 3 और 5 के मान वाले नोड्स को फ्लिप करते हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
एक पुनरावर्ती फ़ंक्शन हल करें () को परिभाषित करें, इसमें दो पेड़ t1 और t2 लगेंगे।
-
यदि रूट1 और रूट2 शून्य हैं, तो सही लौटें
-
अन्यथा जब रूट 1 शून्य है या रूट 2 शून्य है, तो झूठी वापसी करें
-
अन्यथा जब (t1 और t2 दोनों में कोई लेफ्ट सबट्री नहीं है) या (t1 और t2 दोनों में लेफ्ट सबट्री है, और इन दोनों नोड्स के लेफ्ट सबट्री के मान समान हैं), तब
-
हल करें (रूट के बाएं, रूट 2 के बाएं) और हल करें (रूट के दाएं 1, रूट 2 के दाएं)
-
-
अन्यथा
-
हल करें (रूट का बायां, रूट का दायां 2) और हल करें (रूट का दायां 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