इस समस्या में हमें एक बाइनरी ट्री दिया जाता है। हमारा कार्य बाइनरी ट्री में किसी दिए गए नोड का दर्पण खोजना है। हमें एक नोड दिया जाएगा, और उस नोड की मिरर इमेज को विपरीत सबट्री में ढूंढा जाएगा।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
आउटपुट
mirror of B is E.
समाधान दृष्टिकोण
समस्या को हल करने का एक सरल उपाय है रूट से रिकर्सन का उपयोग करके बाएं सबट्री और राइट सबट्री के लिए दो पॉइंटर्स का उपयोग करना। फिर लक्ष्य मान के लिए यदि कोई दर्पण पाया जाता है तो दर्पण को वापस कर दें अन्यथा अन्य नोड्स की पुनरावृत्ति करें।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
उदाहरण
#include <bits/stdc++.h>
using namespace std;
struct Node {
int key;
struct Node* left, *right;
};
struct Node* newNode(int key){
struct Node* n = (struct Node*) malloc(sizeof(struct Node*));
if (n != NULL){
n->key = key;
n->left = NULL;
n->right = NULL;
return n;
}
else{
cout << "Memory allocation failed!"
<< endl;
exit(1);
}
}
int mirrorNodeRecur(int node, struct Node* left, struct Node* right){
if (left == NULL || right == NULL)
return 0;
if (left->key == node)
return right->key;
if (right->key == node)
return left->key;
int mirrorNode = mirrorNodeRecur(node, left->left, right->right);
if (mirrorNode)
return mirrorNode;
mirrorNodeRecur(node, left->right, right->left);
}
int findMirrorNodeBT(struct Node* root, int node) {
if (root == NULL)
return 0;
if (root->key == node)
return node;
return mirrorNodeRecur(node, root->left, root->right);
}
int main() {
struct Node* root = newNode(1);
root-> left = newNode(2);
root->left->left = newNode(3);
root->left->left->left = newNode(4);
root->left->left->right = newNode(5);
root->right = newNode(6);
root->right->left = newNode(7);
root->right->right = newNode(8);
int node = root->left->key;
int mirrorNode = findMirrorNodeBT(root, node);
cout<<"The node is root->left, value : "<<node<<endl;
if (mirrorNode)
cout<<"The Mirror of Node "<<node<<" in the binary tree is
Node "<<mirrorNode;
else
cout<<"The Mirror of Node "<<node<<" in the binary tree is
not present!";
node = root->left->left->right->key;
mirrorNode = findMirrorNodeBT(root, node);
cout<<"\n\nThe node is root->left->left->right, value :
"<<node<<endl;
if (mirrorNode)
cout<<"The Mirror of Node "<<node<<" in the binary tree is
Node "<<mirrorNode;
else
cout<<"The Mirror of Node "<<node<<" in the binary tree is
not present!";
} आउटपुट
The node is root->left, value : 2 The Mirror of Node 2 in the binary tree is Node 6 The node is root->left->left->right, value : 5 The Mirror of Node 5 in the binary tree is not present!