C++で二分木内の任意の2つのノード間のパスのXORを求める

この問題では、二分木とその木に含まれる2つのノードが与えられます。求めるのは、この2つのノードを結ぶパス上に存在するすべてのノードの値のXOR（排他的論理和）です。

具体例を使って問題を確認しましょう。

        1
      /   \
     6     3
    / \   / \
   2   4 7   5

上の二分木において、ノード2からノード3までのパス上の全ノードのXORを求めます。

ノード2からノード3へのパスは「2 → 6 → 1 → 3」です。

この解法では、ルートから各ノードまでの累積XORを利用します。path[2] = 1 ⊕ 6 ⊕ 2 = 5、path[3] = 1 ⊕ 3 = 2 となり、両者のXORを取ると 5 ⊕ 2 = 7 が得られます。なお、最小共通祖先（この例ではノード1）にあたる部分は両方の累積XORに共通して含まれるため打ち消され、実質的には「2 ⊕ 6 ⊕ 3 = 7」が計算されます。

出力 −

7

解法の考え方

この問題を解くには、一方のノードからもう一方のノードへのパスを特定する必要があります。ここでは、ルートから対象の2つのノードそれぞれまでのパスに含まれるノードの累積XORを、前順走査（DFS）で求めていきます。

ルートから走査する場合、始点ノードと終点ノードがルートの同じ側にあるか、異なる側にあるかの2つの場合が考えられます。しかし、どちらの場合でも「ルートから最小共通祖先（LCA）までの区間」は両方の累積XORに共通して含まれます。XORには x ⊕ x = 0 という性質があるため、この共通部分は自動的に打ち消され、結果として2つのノード間のパス部分のXORだけが残ります。

具体的な手順は以下の通りです。

• ルートから各ノードへDFSで降りながら、それまでの累積XORと現在のノード値とのXORを計算し、「ノードの値 → 累積XOR」の対応をハッシュマップに記録します。
• 累積XORを再帰呼び出しの引数として渡すことで、追加の配列などを持たずに済み、メモリ使用量を抑えることができます。
• クエリへの回答は、path[node1] ⊕ path[node2] を返すだけで完了します。

実装例

上記の解法を実装したプログラムは以下の通りです。

#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<<"ツリー内のノード "<<source<<" から "<<destination<<" までのすべてのノードのXOR : ";
    cout<<findPathXOR(mp, source, destination);
    return 0;
}

出力

ツリー内のノード2からノード3までのすべてのノードのXOR : 7

計算量

• 時間計算量： O(N) ― 各ノードを一度ずつ訪問するためです。
• 空間計算量： O(N) ― ハッシュマップの格納領域と再帰呼び出しのスタックが必要になります。