Trong bài toán này, chúng ta được đưa ra một cây nhị phân và hai nút của cây nhị phân. Nhiệm vụ của chúng ta là in XOR của tất cả các nút nằm trong đường dẫn giữa hai nút.
Hãy lấy một ví dụ để hiểu vấn đề,
Chúng ta cần tìm xor của tất cả các nút từ 2 đến 3.
Đường dẫn từ 2 đến 3, 2 → 6 → 1 → 3.
Chúng tôi sẽ tìm thấy 2 ^ 3 ^ 1 ^ 3.
Đầu ra -
Để giải quyết vấn đề này, chúng ta cần tìm các đường dẫn từ nút này đến nút khác. Đối với điều này, chúng tôi sẽ tìm XOR của tất cả các nút trong đường dẫn từ gốc đến cả hai nút. Khi làm điều này, có hai trường hợp khi đi qua nút gốc, cả nút nguồn và nút đích đều nằm trên cùng một phía của nút gốc hoặc chúng nằm ở các phía khác nhau của nút gốc. Trong trường hợp đầu tiên, tất cả các nút không đi vào đường dẫn sẽ được duyệt hai lần và sẽ bị hủy bỏ. Và trong trường hợp trước đây, toàn bộ đường dẫn từ gốc đến các nút cần phải được xem xét lại. Ở mỗi bước, chúng tôi sẽ tìm XOR của nút với kết quả XOR đã tìm thấy trước đó, điều này sẽ tiết kiệm dung lượng.
Ví dụ
Chương trình cho thấy việc triển khai giải pháp của chúng tôi,
#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;
} Đầu ra
The XOR of all node from 2 to 3 of the tree is : 7