इस समस्या में, हमें एक बाइनरी ट्री और बाइनरी ट्री के दो नोड्स दिए गए हैं। हमारा कार्य उन सभी नोड्स का XOR प्रिंट करना है जो दो नोड्स के बीच पथ में आते हैं।
आइए एक उदाहरण से समस्या को समझते हैं,
हमें 2 और 3 के बीच सभी नोड्स का XOR खोजने की आवश्यकता है।
2 से 3 तक का पथ, 2 → 6 → 1 → 3।
हम 2^3^1^3 खोजेंगे।
आउटपुट -
इस समस्या को हल करने के लिए, हमें एक नोड से दूसरे नोड तक के पथ खोजने की आवश्यकता है। इसके लिए, हम रूट से दोनों नोड्स तक के पथ में सभी नोड्स का XOR ढूंढेंगे। ऐसा करने पर रूट नोड से पार करते समय दो मामले होते हैं, या तो स्रोत और गंतव्य नोड दोनों रूट नोड के एक ही तरफ होते हैं या वे रूट नोड के अलग-अलग तरफ होते हैं। पहले मामले में, पथ में नहीं आने वाले सभी नोड्स दो बार पार किए जाएंगे और कैंसिल हो जाएंगे। और पूर्व मामले में रूट से नोड्स तक का पूरा पथ विचार करने की आवश्यकता है। प्रत्येक चरण में हम नोड का 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
