PythonでMin-maxゲーム木を埋めるプログラムの書き方

二人対戦ゲームの局面を表す二分木を考えてみましょう。すべての内部ノードは 0 で初期化されており、葉ノードの値がその局面の最終スコアを表しています。プレイヤー1は最終スコアを最大化することを目指し、プレイヤー2は最小化することを目指します。プレイヤー1は必ず偶数レベル（ルートをレベル0とする）のノードで手を打ち、プレイヤー2は奇数レベルのノードで手を打つものとします。

このとき、両プレイヤーが最適な手を打った場合の結果スコアで、二分木の各ノードを埋めていく必要があります。

たとえば、次のような入力が与えられた場合：

出力は次のようになります：

解決のアプローチ

この問題は、Min-max法として知られる古典的なゲーム木探索アルゴリズムを使って解くことができます。手順は以下の通りです。

• 補助関数 helper() を定義します。引数は root（現在のノード）、h（木の高さ）、currentHeight（現在の深さ）です。
  • root が空（None）なら何もせず return する
  • 左の子に対して helper(左の子, h, currentHeight + 1) を再帰呼び出しする
  • 右の子に対して helper(右の子, h, currentHeight + 1) を再帰呼び出しする
  • currentHeight < h の場合（＝葉ノードでない場合）：
    • currentHeight が偶数（プレイヤー1の手番）なら、子ノードの値の最大値を現在のノードに代入する
      • 左右どちらも存在すれば max(左の値, 右の値)
      • 左の子だけ存在すれば左の子の値
      • 右の子だけ存在すれば右の子の値
    • currentHeight が奇数（プレイヤー2の手番）なら、子ノードの値の最小値を現在のノードに代入する（子の存在チェックのロジックは上記と同じ）
• 木の高さを求める関数 height() を定義します。
  • root が null なら 0 を返す
  • それ以外は 1 + max(height(左), height(右)) を返す
• メイン処理では以下を行います：
  • h := height(root) で木の高さを取得
  • helper(root, h, 0) を呼び出して木を更新
  • root を返す

ポイントはボトムアップ（帰りがけ順）で処理している点です。まず子ノードを再帰的に確定させてから親ノードの値を計算するため、葉のスコアから正しく伝播させることができます。

実装例

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


class Solution:
   def helper(self, root, h, currentHeight):
      if not root:
         return
      self.helper(root.left, h, currentHeight + 1)
      self.helper(root.right, h, currentHeight + 1)
      if currentHeight < h:
         if currentHeight % 2 == 0:
            # 偶数レベル：プレイヤー1（最大化側）
            if root.left and root.right:
               root.val = max(root.left.val, root.right.val)
            elif root.left:
               root.val = root.left.val
            elif root.right:
               root.val = root.right.val
         else:
            # 奇数レベル：プレイヤー2（最小化側）
            if root.left and root.right:
               root.val = min(root.left.val, root.right.val)
            elif root.left:
               root.val = root.left.val
            elif root.right:
               root.val = root.right.val

   def height(self, root):
      if not root:
         return 0
      return 1 + max(self.height(root.left), self.height(root.right))

   def solve(self, root):
      h = self.height(root)
      self.helper(root, h, 0)
      return root


def print_tree(root):
   if root is not None:
      print_tree(root.left)
      print(root.val, end=', ')
      print_tree(root.right)


ob = Solution()
root = TreeNode(0)
root.left = TreeNode(3)
root.right = TreeNode(0)
root.right.left = TreeNode(0)
root.right.right = TreeNode(0)
root.right.left.left = TreeNode(-3)
root.right.right.right = TreeNode(4)
print_tree(ob.solve(root))

入力

root = TreeNode(0)
root.left = TreeNode(3)
root.right = TreeNode(0)
root.right.left = TreeNode(0)
root.right.right = TreeNode(0)
root.right.left.left = TreeNode(-3)
root.right.right.right = TreeNode(4)

出力

3, 3, -3, -3, -3, 4, 4,

動作の解説

この例では、レベル0（ルート）とレベル2がプレイヤー1の手番（最大化）、レベル1がプレイヤー2の手番（最小化）に相当します。

• 葉ノードの値（3、-3、4）はそのまま維持されます。
• レベル2のノードは子の値をそのまま引き継ぎます（片方しか子がないため）。
• レベル1のノードは子の最小値を選びます。左側のノードは min(3, -3) = -3、右側のノードは min(-3, 4) = -3 となります。
• ルート（レベル0）は子の最大値を選び、max(3, -3) = 3 となります。

この結果、両者が最適にプレイした場合のゲームの価値は 3 であることが分かります。

計算量

• 時間計算量： O(n) — 各ノードをちょうど1回ずつ訪問します（n はノード数）。
• 空間計算量： O(h) — 再帰呼び出しのスタックが木の高さ h に比例して積まれます。