【C++】ルートからリーフへの経路上に、合計がルートの値と一致するノードのペアが存在するか判定する方法

この問題では、二分木（Binary Tree）が与えられます。求められているのは、「ルートからリーフ（葉）に至る経路上に、2つのノードの値の合計がルートのデータと等しくなるペアが存在するかどうか」を判定することです。

つまり、ルートノードからリーフノードまでの間にあるノードの中から2つを選んだとき、その値の合計がルートノードの値と一致するような組み合わせが存在するかをチェックします。

問題例で理解しよう

入力：

出力： Yes

説明：

ルートノードの値は 7 です。

合計が7になるペアとして、(2, 5) と (1, 6) が存在します。

解決アプローチ：ハッシュを活用した探索

木を走査しながら、ハッシュセットを使って効率的にペアを探します。

手順は以下の通りです。

1. 空のハッシュセット（hashTable）を用意します。
2. ルートの子からリーフへ向かって深さ優先探索（DFS）を行います。
3. 各ノードに到達した時点で、「ルートの値 − 現在のノードの値」に相当する値がすでにハッシュセット内に存在するかを確認します。存在すれば、合計がルートの値と一致するペアが見つかったことになります。
4. ペアが見つからなければ、現在のノードの値をハッシュセットに追加して子ノードへ進みます。
5. 子の探索が終わったら、現在のノードの値をハッシュセットから削除（バックトラック）します。これにより、常に「現在の経路上のノードの値だけ」がセットに保持されます。
6. 最後まで探索してもペアが見つからなければ false を返し、見つかれば true を返します。

解法の動作を示すプログラム

コード例

#include<bits/stdc++.h>
using namespace std;

struct Node {

    int data;
    struct Node* left, *right;
};

struct Node* newnode(int data) {

    struct Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return (node);
}

bool findSumUntill(Node *node, unordered_set<int> &hashTable, int rootVal)
{
    if (node == NULL)
       return false;

    int otherVal = rootVal - node->data;
    if (hashTable.find(otherVal) != hashTable.end())
       return true;

    hashTable.insert(node->data);
    bool isFound = findSumUntill(node->left, hashTable, rootVal) || findSumUntill(node->right, hashTable, rootVal);
    hashTable.erase(node->data);

    return isFound;
}

bool findPairSum(Node *root) {

    unordered_set<int> hashTable;

    return findSumUntill(root->left, hashTable, root->data) || findSumUntill(root->right, hashTable, root->data);
}

int main()
{
    struct Node *root = newnode(7);
    root->left = newnode(2);
    root->right = newnode(3);
    root->left->left = newnode(5);
    root->left->right = newnode(9);
    root->left->left->left = newnode(1);
    root->left->left->right = newnode(6);
    root->right->left = newnode(8);

    if(findPairSum(root))
       cout<<"Pair with sum equal to root value found";
    else
       cout<<"No pairs found";
    return 0;
}

出力

Pair with sum equal to root value found

プログラムのポイント

この実装の重要な点は、再帰呼び出しから戻る際に hashTable.erase(node->data) を呼び出しているところです。これにより、ハッシュセットには常に「現在探索中のルートからリーフへの1本の経路上のノードの値」のみが格納され、別の枝のノードと誤ってペア判定されることを防いでいます。

また、探索はルート自身ではなく root->left と root->right から開始しています。これは、ペアの候補となるノードが「ルート以外の経路上のノード」であるためです。

計算量

時間計算量： O(N) ― 各ノードを最大1回ずつ訪問し、ハッシュ操作は平均O(1)です。
空間計算量： O(H) ― ハッシュセットには経路上のノード数（木の高さH分）しか値が保持されず、再帰スタックもO(H)です。