इस समस्या में, हमें एक बाइनरी ट्री दिया जाता है। हमारा कार्य बाइनरी ट्री में दिए गए नोड का मिरर ढूंढना है। हमें एक नोड दिया जाएगा, और उस नोड का मिरर इमेज विपरीत सबट्री में ढूंढना होगा।
आइए एक उदाहरण से समस्या को समझते हैं,
इनपुट
आउटपुट
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!
