C++의 이진 트리에 있는 두 노드 간의 경로 XOR

이 문제에서는 이진 트리와 이진 트리의 두 노드가 제공됩니다. 우리의 임무는 두 노드 사이의 경로에 있는 모든 노드의 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