C++で二分木内の合計がKとなるすべてのパスを出力する方法

この問題では、二分木と数値Kが与えられ、パス上のノード値の合計がKに等しくなるような、木の中のすべてのパスを出力することが求められます。

ここでいうパスとは、木の任意のノードから始まり、任意のノードで終わることができるものです。ただし、パスは必ず親ノードから子ノードへ向かう(下向きの)方向である必要があります。また、ノードの値は正・負・ゼロのいずれであっても構いません。

具体例を使って問題を理解しましょう。

K = 5 の場合

出力:

1 3 1
3 2
1 4

解き方のアプローチ

この問題を解くためには、各ノードを一時的な根(ルート)として扱い、そこから下方向へ伸びる経路のうち、ノード値の合計がKになるものを探します。

経路上のすべてのノードをvectorに格納しながら探索を進め、現在のノードから順に遡って累積和を計算します。その合計がKと一致するたびに、該当する区間をパスとして出力します。

C++での実装例

以下は、このアルゴリズムを実装したプログラムです。

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    Node *left,*right;
    Node(int x){
        data = x;
        left = right = NULL;
    }
};
void printPath(const vector<int>& v, int i) {
    for (int j=i; j<v.size(); j++)
        cout<<v[j]<<"\t";
    cout<<"\n";
}
void findKSumPath(Node *root, vector<int>& path, int k) {
    if (!root)
        return;
    path.push_back(root->data);
    findKSumPath(root->left, path, k);
    findKSumPath(root->right, path, k);
    int f = 0;
    for (int j=path.size()-1; j>=0; j--){
        f += path[j];
        if (f == k)
            printPath(path, j);
    }
    path.pop_back();
}
int main() {
    Node *root = new Node(1);
    root->left = new Node(3);
    root->left->left = new Node(1);
    root->left->right = new Node(2);
    root->right = new Node(4);
    root->right->right = new Node(7);
    int k = 5;
    cout<<"Paths with sum "<<k<<" are :\n";
    vector<int> path;
    findKSumPath(root, path, k);
    return 0;
}

出力結果

Paths with sum 5 are −
1 3 1
3 2
1 4

計算量について

このアルゴリズムの計算量は、最悪の場合O(n²)となります(nはノード数)。これは、各ノードを訪問するたびに経路を遡って合計を計算する必要があるためです。

より効率化したい場合は、根からの累積和(prefix sum)とハッシュマップを組み合わせることで、全体の計算量をO(n)まで改善できることが知られています。負の値も含まれる木では、単純な枝刈りが使えないため、この手法が特に有効です。