用 Python 编写填充 Min-max 游戏树的程序

pythonserver side programmingprogramming

假设我们有一棵二叉树，表示双人游戏的游戏状态。每个内部节点都填充 0，叶子值表示最终得分。玩家 1 希望最大化最终得分，而玩家 2 希望最小化最终得分。玩家 1 总是在偶数级别的节点上移动，而玩家 2 总是在奇数级别的节点上移动。我们必须用假设两个玩家都发挥最佳的结果得分来填充二叉树。

因此，如果输入如下

那么输出将是

为了解决这个问题，我们将遵循以下步骤 −

定义一个函数 helper() 。这将获取 root、h、currentHeight
如果 root 为空，则
- 返回
helper(root 左侧、h、currentHeight + 1)
helper(root 右侧、h、currentHeight + 1)

如果 currentHeight < h，则

如果 currentHeight 为偶数，则

如果根的左侧和右侧不为空，则
- 根的值 := 根左侧值的最大值，根右侧的值
否则，当根的左侧不为空时，则
- 根的值 := 根左侧的值
否则，当根的右侧不为空时，则
- 根的值 := 根右侧的值
否则，
- 如果根的左侧和右侧不为空，则
  - 根的值 := 根左侧值的最小值，根右侧的值根
- 否则，当根的左侧不为空时，则
  - 根的值 := 根左侧的值
- 否则，当根的右侧不为空时，则
  - 根的值 := 根右侧的值
定义一个函数 height() 。这将使 root 生效
如果 root 为空，则
- 返回 0
返回 1 + (高度的最大值(根的左侧)，高度(根的右侧))
从主方法中，执行以下操作 −
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)