Pythonで二分木の根から葉までの最長経路の合計値を求めるプログラム

二分木が与えられたとき、根（ルート）から葉ノードまでの最長経路におけるノード値の合計を求める問題を考えます。同じ長さの経路が複数存在する場合は、その中で合計値が大きい方の経路を採用します。

たとえば、次のような二分木が入力として与えられた場合を考えてみましょう。

この場合、出力は 20 になります。

解き方のアプローチ

この問題は、再帰を使って各ノードから「深さ」と「合計値」のペアを返すことで解けます。手順は以下の通りです。

• 関数 rec() を定義します。引数として現在のノード curr を受け取ります。
• curr が null（空）の場合は、ペア (0, 0) を返します。
• bigger := 左の子に対する rec() の結果と右の子に対する rec() の結果の最大値を取ります。
• ペア (bigger[0] + 1, bigger[1] + curr の値) を返します。第一要素は深さ、第二要素はそこまでの合計値です。

メインメソッドでの処理

• ret := rec(root) を実行します。
• ret のインデックス1（合計値）を返します。

ポイントは、タプル同士の比較ではまず第一要素（深さ）が比較され、等しい場合は第二要素（合計値）が比較されるというPythonの仕様を利用している点です。これにより、「より深い経路を優先し、深さが同じなら合計値が大きい方を選ぶ」という条件を自然に実現できます。

実装例

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

class Solution:
    def solve(self, root):
        def rec(curr):
            if not curr:
                return (0, 0)
            bigger = max(rec(curr.left), rec(curr.right))
            return (bigger[0] + 1, bigger[1] + curr.val)
        return rec(root)[1]
ob = Solution()
root = TreeNode(2)
root.left = TreeNode(10)
root.right = TreeNode(4)
root.right.left = TreeNode(8)
root.right.right = TreeNode(2)
root.right.left.left = TreeNode(6)
print(ob.solve(root))

入力

root = TreeNode(2)
root.left = TreeNode(10)
root.right = TreeNode(4)
root.right.left = TreeNode(8)
root.right.right = TreeNode(2)
root.right.left.left = TreeNode(6)

出力

20

この例では、根から最も深い葉までの経路は「2 → 4 → 8 → 6」であり、その合計値は 2 + 4 + 8 + 6 = 20 となります。計算量は各ノードを一度だけ訪問するため O(N)、再帰によるスタック消費を含めた空間計算量は木の高さに依存し、最悪ケースで O(N) です。