इस समस्या में हमें एक बाइनरी ट्री और बाइनरी ट्री के दो नोड दिए जाते हैं। हमारा काम दो नोड्स के बीच के रास्ते में आने वाले सभी नोड्स के XOR को प्रिंट करना है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
हमें 2 और 3 के बीच के सभी नोड्स के xor को खोजने की जरूरत है।
2 से 3 तक का रास्ता, 2 → 6 → 1 → 3.
हमें 2^3^1^3 मिलेगा।
आउटपुट -
इस समस्या को हल करने के लिए, हमें एक से दूसरे नोड तक के रास्ते खोजने होंगे। ऐसा करने के लिए, हम रूट से दोनों नोड्स के रास्ते में सभी नोड्स के एक्सओआर पाएंगे। ऐसा करने पर रूट नोड से ट्रैवर्स करते समय दो मामले होते हैं, या तो स्रोत और गंतव्य नोड दोनों रूट नोड के एक ही तरफ स्थित होते हैं या वे रूट नोड के विभिन्न किनारों पर स्थित होते हैं। पहले मामले में, रास्ते में नहीं आने वाले सभी नोड्स को दो बार ट्रैवर्स किया जाएगा और रद्द कर दिया जाएगा। और पूर्व मामले में रूट से नोड्स तक पूरे पथ पर विचार करने की आवश्यकता है। प्रत्येक चरण में हम पिछले पाए गए XOR परिणाम के साथ नोड का XOR पाएंगे, इससे स्थान की बचत होगी।
उदाहरण
हमारे समाधान के कार्यान्वयन को दिखाने के लिए कार्यक्रम,
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *left, *right;
};
struct Node* getNode(int data){
struct Node* newNode = new Node;
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
void pathStoD(Node* root, unordered_map<int, int>& path, int XOR){
if (!root)
return;
path.insert(make_pair(root->data, XOR ^ root->data));
XOR ^= root->data;
if (root->left)
pathStoD(root->left, path, XOR);
if (root->right)
pathStoD(root->right, path, XOR);
}
int findPathXOR(unordered_map<int, int> path, int node1, int node2){
return path[node1] ^ path[node2];
}
int main(){
struct Node* root = getNode(1);
root->left = getNode(6);
root->left->left = getNode(2);
root->left->right = getNode(4);
root->right = getNode(3);
root->right->left = getNode(7);
root->right->right = getNode(5);
int XOR = 0;
unordered_map<int, int> mp;
int source = 2;
int destination = 3;
pathStoD(root, mp, XOR);
cout<<"The XOR of all node from "<<source<<" to "<<destination<<" of the tree is : ";
cout<<findPathXOR(mp, source, destination);
return 0;
} आउटपुट
The XOR of all node from 2 to 3 of the tree is : 7