Pythonで二分木の隣接しないノードの最大合計を求めるアルゴリズム

問題の概要

二分木が与えられたとき、親子関係にある2つのノードを同時に選ばないという制約のもとで、選択できるノードの値の合計の最大値を求める問題を考えてみましょう。

例えば、次のような二分木が入力として与えられたとします。

この場合、出力は 17 になります。これは、10、4、3 の3つのノードは互いに親子関係（隣接関係）にないため、すべて選択できるからです。

解き方のアプローチ

この問題は、各ノードについて「そのノードを選ぶ場合」と「選ばない場合」の2つの状態を再帰的に計算することで解けます。手順は以下の通りです。

• 関数 f() を定義します。引数としてノードを受け取ります。
• ノードが null（存在しない）場合は、(0, 0) を返します。
• (a, b) := f(左の子ノード) として、左側部分木の結果を取得します。
• (c, d) := f(右の子ノード) として、右側部分木の結果を取得します。
• 次のペアを返します：(max(現在のノードの値 + b + d, a + c), a + c)
  ・第1要素：現在のノードを選ぶ場合（子の「選ばない場合の値」b + d を加算）と、選ばない場合（a + c）の大きい方
  ・第2要素：現在のノードを選ばなかった場合の合計
• メイン処理から f(root) を呼び出し、その戻り値の最初の要素を返します。

ここで重要なのは、あるノードを選んだ場合、その直下の子ノードは選べないため、子の「選ばなかった場合の値」だけを足し合わせる点です。逆にノードを選ばない場合は、子の結果の最大値（選ぶ・選ばないのいずれか大きい方）を利用できます。

実装例

以下のコードで実際の動作を確認してみましょう。

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

def f(node):
    if not node:
        return 0, 0
    a, b = f(node.left)
    c, d = f(node.right)
    return max(node.val + b + d, a + c), a + c

class Solution:
    def solve(self, root):
        return f(root)[0]

ob = Solution()
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(10)
root.left.left = TreeNode(4)
root.left.right = TreeNode(3)
print(ob.solve(root))

入力

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(10)
root.left.left = TreeNode(4)
root.left.right = TreeNode(3)

出力

17

計算の流れを確認

この例では、ルート（1）を選ぶと子ノード（2 と 10）は選択できません。一方、ルートを選ばなければ、10 + 4 + 3 = 17 となります。これが最大値となるため、出力は 17 になります。

この手法の計算量は O(n)（n はノード数）であり、各ノードを一度だけ訪問するため効率的です。また、「ハウスロバー問題（House Robber）」の木構造版として知られる定番の動的計画法・再帰の応用問題でもあります。