C++で二分木における指定された合計を持つルートからのパスをすべて出力する方法

この問題では、二分木とある合計値 S が与えられます。求めるのは、ルート（根）から木の任意のノードまで辿ったとき、経路上のノード値の合計が指定された値と一致するようなパスです。条件を満たすパスは複数存在する場合があるため、該当するすべてのパスを出力します。

入力例

Sum = 14
Output : path : 4 10
4 3 7

解法のアプローチ

この問題を解くには、二分木の先行順走査（プリオーダートラバーサル）を利用します。ルートから各ノードへ向かう途中で、それまでに通過したノード値の累積和（sum_so_far）を記録し、それが目的の合計と一致した時点で、そこまでのパスを出力します。

アルゴリズムの手順

1. 現在のノードの値を累積和に加算し、パスに追加します。
2. 累積和が指定された合計と一致したら、パスの内容を出力します。
3. 左の子ノード・右の子ノードに対して、再帰的に同じ処理を繰り返します。
4. 再帰から戻る際には、パスから現在のノードを取り除きます（バックトラッキング）。

C++での実装例

#include<bits/stdc++.h>
using namespace std;
struct Node{
    int key;
    struct Node *left, *right;
};
Node* insertNode(int key){
    Node* temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return (temp);
}
void printPathsUtilSum(Node* curr_node, int sum, int sum_so_far, vector<int> &path){
    if (curr_node == NULL)
        return;
    sum_so_far += curr_node->key;
    path.push_back(curr_node->key);
    if (sum_so_far == sum ){
        for (int i=0; i<path.size(); i++)
            cout<<path[i]<<"\t";
        cout<<endl;
    }
    if (curr_node->left != NULL)
        printPathsUtilSum(curr_node->left, sum, sum_so_far, path);
    if (curr_node->right != NULL)
        printPathsUtilSum(curr_node->right, sum, sum_so_far, path);
    path.pop_back();
}
void pathWithSum(Node *root, int sum){
    vector<int> path;
    printPathsUtilSum(root, sum, 0, path);
}
int main (){
    Node *root = insertNode(4);
    root->left = insertNode(10);
    root->right = insertNode(3);
    root->right->left = insertNode(7);
    root->right->right = insertNode(1);
    root->left->left = insertNode(8);
    root->left->right = insertNode(6);
    int sum = 14;
    cout<<"Paths with the given sum are : "<<endl;
    pathWithSum(root, sum);
    return 0;
}

実行結果

合計が 14 となるパスは、次のように出力されます。

4 10
4 3 7

計算量について

時間計算量は O(n²) となります。これは、最悪の場合、各ノードで条件を満たしたパスの出力に最大 O(n) を要するためです。また、空間計算量は O(h)（h は木の高さ）で、再帰スタックおよびパスを保持するベクターによるものです。