Pythonで二分木の任意の2ノード間における最大パス合計を求めるプログラム

二分木の最大パス合計とは

二分木が与えられたとき、任意の2つのノードをつなぐパスの中で、ノードの値の合計が最大になるものを求める問題です。ここでいう「パス」とは、木の中で隣接するノード同士を順にたどる経路のことで、必ずしも根（ルート）から始まる必要はありません。

例として、次のような二分木を考えてみましょう。

この場合、最適なパスは [12, 13, 14, 16, 7] となるため、出力される答えは 62 になります。

解法のアプローチ

この問題は再帰（深さ優先探索）を使って効率的に解くことができます。各ノードに対して「そのノードを端点とする片側だけの最大合計」と「そのノードを折り返し点とした両側を含む最大合計」の2つを考え、後者で全体の答えを更新していくのがポイントです。

アルゴリズムの手順

1. 補助関数 utils() を定義します。引数には現在のノード（root）を受け取ります。
2. root が null（None）の場合は 0 を返します。
3. 左部分木の結果を l、右部分木の結果を r として再帰的に取得します。ただし、負の値はパスに含める意味がないため、0 と比較して切り捨てます。
4. max_single を「左右どちらか大きい方に自分の値を足したもの」と「自分の値のみ」の最大値として計算します。これは親に渡せる片側パスの最大値です。
5. max_top を「max_single」と「l + r + 自分の値（左右両方を使うパス）」の最大値として計算します。
6. 全体の答え res を max_top と比較して更新します。
7. max_single を親ノードに返します。

メイン処理の流れ

• root が null の場合は 0 を返します。
• res を負の無限大（-inf）で初期化します。
• utils(root) を呼び出します。
• res の値を返します。

Pythonでの実装例

それでは、実際のコードを見てみましょう。

class TreeNode:
    def __init__(self, value):
        self.val = value
        self.left = None
        self.right = None

class Solution:
    def solve(self, root):
        if root is None:
            return 0
        self.res = float("-inf")
        self.utils(root)
        return self.res

    def utils(self, root):
        if root is None:
            return 0
        # 左右の部分木から得られる最大合計（負なら0として扱う）
        l = max(self.utils(root.left), 0)
        r = max(self.utils(root.right), 0)
        # 親に渡せる「片側だけ」のパスの最大値
        max_single = max(max(l, r) + root.val, root.val)
        # 現在のノードを折り返し点とする「両側」のパスの最大値
        max_top = max(max_single, l + r + root.val)
        # 全体の答えを更新
        self.res = max(self.res, max_top)
        return max_single

ob = Solution()
root = TreeNode(13)
root.left = TreeNode(12)
root.right = TreeNode(14)
root.right.left = TreeNode(16)
root.right.right = TreeNode(22)
root.right.left.left = TreeNode(4)
root.right.left.right = TreeNode(7)
print(ob.solve(root))

入力

root = TreeNode(13)
root.left = TreeNode(12)
root.right = TreeNode(14)
root.right.left = TreeNode(16)
root.right.right = TreeNode(22)
root.right.left.left = TreeNode(4)
root.right.left.right = TreeNode(7)

出力

62

計算量について

このアルゴリズムは各ノードを一度だけ訪問するため、時間計算量は O(N)（Nはノード数）、空間計算量は再帰の深さに依存して O(H)（Hは木の高さ）となります。最悪の場合（木が一直線につながっている場合）は O(N) のスタック領域が必要になる点に注意してください。

まとめ

二分木の最大パス合計問題は、再帰を使って各ノードで「片側パス」と「両側パス」を区別しながら答えを更新していくのが定石です。負の値を持つノードが存在しても正しく動作するよう、部分木の寄与が負になる場合は 0 として扱うことが重要なポイントです。