दो बाइनरी ट्री source और target दिए गए हैं। जांचें कि क्या source का कोई उल्टा रूप (inversion) target का उपट्री है। उल्टा रूप का अर्थ: बाएं और दाएं बच्चे वैकल्पिक रूप से स्वैप हो सकते हैं।
रिकर्सिव जांच: दो ट्री उल्टे हैं यदि (बाएं-बाएं और दाएं-दाएं मेल खाते हैं) या (बाएं-दाएं और दाएं-बाएं मेल खाते हैं)। target के प्रत्येक नोड पर यह जांच करें।
उदाहरण: दिए गए source और target के लिए आउटपुट true (1)।
C++ कार्यान्वयन
#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);
}
};
int 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);
return 0;
}
इनपुट
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