使用Python填写Min-max游戏树的程序
假设我们有一棵二叉树表示两人游戏的游戏状态。每个内部节点填充为0,叶子节点的值表示最终得分。玩家1想要最大化最终得分,而玩家2想要最小化最终得分。玩家1将始终在偶数层的节点上进行移动,而玩家2将始终在奇数层的节点上进行移动。我们必须根据假设的最佳玩家策略来填充二叉树的所有节点。
因此,如果输入如下所示:
则输出将如下所示:
为了解决这个问题,我们将执行以下步骤−
- 定义一个函数helper()。这将接受根节点(root)、高度(h)和当前高度(currentHeight)。
- 如果根节点(root)为空,则
- 返回
- helper(根的左子节点, h, currentHeight + 1)
- helper(根的右子节点, h, currentHeight + 1)
- 如果currentHeight < h,则
- 如果currentHeight为偶数,则
- 如果根的左子树和右子树都不为空,则
- 根的值 := 根的左子节点值和根的右子节点值的最大值
- 否则,当根的左子树不为空时,则
- 根的值 := 根的左子节点值
- 否则,当根的右子树不为空时,则
- 根的值 := 根的右子节点值
- 否则,
- 如果根的左子树和右子树都不为空,则
- 根的值 := 根的左子节点值和根的右子节点值的最小值
- 否则,当根的左子树不为空时,则
- 根的值 := 根的左子节点值
- 否则,当根的右子树不为空时,则
- 根的值 := 根的右子节点值
- 如果currentHeight为偶数,则
- 定义一个函数height()。这将接受根节点(root)。
- 如果根节点(root)为空,则
- 返回0
- 返回1 + (左子树高度和右子树高度的最大值)
- 从main方法中,执行以下内容−
- h := height(root)
- helper(root, h, 0)
- 返回root
让我们看下面的实现,以更好地理解。
更多Python相关文章,请阅读:Python 教程
例子
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,