Pythonで二分木のルートからリーフへのパスの最大合計を求めるプログラム

問題概要

二分木（バイナリツリー）が与えられたとき、ルートノードからリーフノードへ至る任意のパスの中で、合計値が最大となるものを求める必要があります。

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

この場合の出力は 29 になります。ルートから「5 → 9 → 7 → 8」というパスを辿ったときの合計が 29 となるためです。

解法のアプローチ

この問題は、深さ優先探索（DFS）を用いて、ルートから各リーフまでのすべてのパスを再帰的に走査することで解けます。具体的な手順は以下のとおりです。

• walk() 関数を定義します。引数として現在のノード node と、そこまでの累積合計 s を受け取ります。
• ノードが null の場合：
  • max_sum と s の大きい方を max_sum に代入します。
  • 処理を終了して呼び出し元に戻ります。
• s に現在のノードのデータを加算します。
• 左の子ノードに対して walk(node.left, s) を呼び出します。
• 右の子ノードに対して walk(node.right, s) を呼び出します。
• メイン処理では以下を行います。
  • max_sum := 0 で初期化します。
  • walk(root, 0) を実行して全パスを走査します。
  • 最終的な max_sum を返します。

実装例

それでは、実際のコードを見ながら理解を深めましょう。

from collections import defaultdict

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

class Solution:
    def walk(self, node, s):
        if not node:
            self.max_sum = max(self.max_sum, s)
            return
        s += node.data
        self.walk(node.left, s)
        self.walk(node.right, s)

    def solve(self, root):
        self.max_sum = 0
        self.walk(root, 0)
        return self.max_sum

ob = Solution()
root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(9)
root.right.left = TreeNode(7)
root.right.right = TreeNode(10)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)
print(ob.solve(root))

入力

root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(9)
root.right.left = TreeNode(7)
root.right.right = TreeNode(10)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)

出力

29

まとめ

このアルゴリズムの計算量は、木の全ノードを一度ずつ訪問するため O(n)、再帰によるスタック消費も最悪で木の高さに比例する O(h) です。負の値を持たないノード構成の場合は常にリーフ到達時に最大値が確定しますが、負の値が含まれる場合は途中打ち切りなどの工夫が必要になる点にも注意しましょう。