C++のバイナリツリー内の任意の2つのノード間のパスのXOR

この問題では、二分木と二分木の2つのノードが与えられます。私たちのタスクは、2つのノード間のパスにあるすべてのノードのXORを出力することです。

問題を理解するために例を見てみましょう

2から3までのすべてのノードの排他的論理和を見つける必要があります。

2から3、2→6→1→3へのパス。

2 ^ 3 ^ 1^3が見つかります。

出力 −

この問題を解決するには、あるノードから別のノードへのパスを見つける必要があります。このために、ルートから両方のノードへのパスにあるすべてのノードのXORを見つけます。これを行う場合、ルートノードからトラバースするときに2つのケースがあります。ソースノードと宛先ノードの両方がルートノードの同じ側にあるか、ルートノードの異なる側にあります。最初のケースでは、パスに含まれないすべてのノードが2回トラバースされ、キャンセルされます。前者の場合、ルートからノードへのパス全体を考慮する必要があります。各ステップで、前に見つかった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