C++で二分木における2つの葉ノード間の最大パス合計を求める方法

問題の概要

この問題では、各ノードが値を持つ二分木が与えられます。私たちのタスクは、二分木における2つの葉ノード（リーフノード）間の最大パス合計を求めるプログラムを作成することです。

ここで求めるのは、値の合計が最大になるような、ある葉ノードから別の葉ノードへのパスです。この最大合計パスには、ルートノードが含まれる場合もあれば、含まれない場合もあります。

二分木（Binary Tree）とは、各ノードが最大2つの子ノードを持つことができる木構造のデータ構造です。それぞれの子ノードは「左の子（left child）」と「右の子（right child）」と呼ばれます。

具体例

以下のような二分木を考えてみましょう。

入力 − 二分木…

出力 − 24

説明 − 葉ノード 2 から 9 へのパスが最大の合計を与えます。その計算は (2 + 5 + 6 - 2 + 4 + 9) = 24 となります。

解法のアプローチ

この問題を解くためには、木を走査（トラバーサル）しながら、現在のノードに対する左部分木・右部分木それぞれの最大合計を記録していきます。同時に、それまでに見つかった「2つの葉ノード間の最大パス」も追跡します。

すべてのノードについて、その部分木における可能な限り最大の「葉から葉へのパス」を求めます。そして、それをこれまでの全体の最大パスと比較し、大きい方の値をグローバルな最大パス合計として保存します。

例を使った解法の確認

先ほどの例をもとに、解法をより深く理解しましょう。

初期状態のグローバル最大合計 = 6（パス 2 → 5 → -1）

次に、6 をルートノードとした場合を確認します。

左部分木の場合 −

葉ノードまでのパスの合計は 7 と 4 です。

最大値は 7（パス 5 → 2）となります。

右部分木の場合 −

葉ノードまでのパスの合計は 5 で、パス（1 → -3 → 7）が1つの候補になります。

以上より、葉ノード間のパスの合計は −

左部分木における「葉からルート（6）までの最大合計」+ ルート + 右部分木における「葉からルート（6）までの最大合計」= 7 + 6 + 5 = 18

グローバル最大パス合計（6）と比較すると、新しいグローバル最大パス合計は 18 に更新されます。

C++での実装例

以下は、2つの葉ノード間の最大パス合計を求めるC++プログラムです。

#include <bits/stdc++.h>
using namespace std;
struct Node{
    int data;
    struct Node* left, *right;
};
struct Node* insertNode(int data){
    struct Node* node = new(struct Node);
    node->data = data;
    node->left = node->right = NULL;
    return (node);
}
int max(int a, int b)
{ return (a >= b)? a: b; }
int maxPathSumLeaf(struct Node *root, int &maxSum){
    if (root==NULL) return 0;
    if (!root->left && !root->right) return root->data;
    int leftSubTree = maxPathSumLeaf(root->left, maxSum);
    int rightSubTree = maxPathSumLeaf(root->right, maxSum);
    if (root->left && root->right){
        maxSum = max(maxSum, leftSubTree + rightSubTree + root->data);
        return max(leftSubTree, rightSubTree) + root->data;
    }
    return (!root->left)? rightSubTree + root->data: leftSubTree + root->data;
}
int main(){
    struct Node *root = insertNode(-2);
    root->left = insertNode(6);
    root->right = insertNode(4);
    root->left->left = insertNode(5);
    root->left->right = insertNode(1);
    root->left->left->left = insertNode(2);
    root->left->left->right = insertNode(-1);
    root->left->right->left = insertNode(-3);
    root->left->right->left->left = insertNode(7);
    root->right->left = insertNode(9);
    root->right->right = insertNode(3);
    int maxSum = INT_MIN;
    maxPathSumLeaf(root, maxSum);
    cout<<"指定された二分木における2つの葉ノード間の最大パス合計は "<<maxSum;
    return 0;
}

出力結果

指定された二分木における2つの葉ノード間の最大パス合計は 24

計算量について

このアルゴリズムの時間計算量は O(n) です。これは、木に含まれる各ノードをちょうど1回ずつ訪問するためです。また、空間計算量は再帰呼び出しのスタックに依存し、木の高さを h とすると O(h) となります。平衡な二分木であれば O(log n)、最悪の場合（線形に連なる木）は O(n) になります。