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,

Arnab Chakraborty

更新于: 2020-11-20

3K+ 浏览量

开启你的 职业生涯

通过完成课程获得认证

立即开始