ในปัญหานี้ เราจะได้รับไบนารีทรีและสองโหนดของไบนารีทรี งานของเราคือพิมพ์ XOR ของโหนดทั้งหมดที่เข้ามาในเส้นทางระหว่างสองโหนด
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
เราต้องหา xor ของโหนดทั้งหมดระหว่าง 2 ถึง 3
เส้นทางจาก 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
