Python 實現極大極小博弈樹填充程式

假設我們有一棵二叉樹，表示一個兩人遊戲的博弈狀態。每個內部節點都填充為 0，葉子節點的值表示最終得分。玩家 1 希望最大化最終得分，而玩家 2 希望最小化最終得分。玩家 1 始終在偶數層節點上進行移動，玩家 2 始終在奇數層節點上進行移動。我們必須在二叉樹中填充結果分數，假設兩位玩家都以最佳方式進行遊戲。

因此，如果輸入類似於

則輸出將是

為了解決這個問題，我們將遵循以下步驟：

  • 定義一個函式 helper()。它將接收根節點 root、樹的高度 h 和當前高度 currentHeight 作為引數。
  • 如果根節點為空，則
    • 返回。
  • 遞迴呼叫 helper(root 的左子節點, h, currentHeight + 1)
  • 遞迴呼叫 helper(root 的右子節點, h, currentHeight + 1)
  • 如果 currentHeight 小於 h，則
    • 如果 currentHeight 為偶數，則
      • 如果 root 的左子節點和右子節點都不為空，則
        • root 的值 := root 的左子節點的值和右子節點的值中的最大值
      • 否則，如果 root 的左子節點不為空，則
        • root 的值 := root 的左子節點的值
      • 否則，如果 root 的右子節點不為空，則
        • root 的值 := root 的右子節點的值
    • 否則，
      • 如果 root 的左子節點和右子節點都不為空，則
        • root 的值 := root 的左子節點的值和右子節點的值中的最小值
      • 否則，如果 root 的左子節點不為空，則
        • root 的值 := root 的左子節點的值
      • 否則，如果 root 的右子節點不為空，則
        • root 的值 := root 的右子節點的值
  • 定義一個函式 height()。它將接收根節點 root 作為引數。
  • 如果 root 為空，則
    • 返回 0。
  • 返回 1 + (root 的左子節點的高度和右子節點的高度中的最大值)
  • 在主方法中，執行以下操作：
  • 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:
               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:
                  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,

更新於: 2020-11-20

3K+ 瀏覽量

開啟你的 職業生涯

透過完成課程獲得認證

立即開始
廣告

© . All rights reserved.