数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学Python二叉树染色游戏
假设有两名玩家在一个二叉树上玩轮流进行的游戏。我们有这棵二叉树的根节点和树中的节点数n。这里n是奇数，每个节点都有一个从1到n的不同值。首先，第一名玩家命名一个值x，其中1 <= x <= n，第二名玩家命名一个值y，其中1 <= y <= n，并且满足条件y != x。第一名玩家将值为x的节点染成红色，第二名玩家将值为y的节点染成蓝色。之后，玩家轮流进行，从第一名玩家开始。在每一轮中，玩家选择一个他们颜色（玩家1为红色，玩家2为蓝色）的节点，并给所选节点的一个未着色的邻居节点染色（选择的节点的左子节点或右子节点，或父节点）。当且仅当玩家无法以这种方式选择节点时，他们必须轮空。如果两名玩家都轮空，游戏结束，染色节点数量较多的玩家获胜。
假设我们是第二名玩家。如果可以选择这样的y来确保我们赢得游戏，则返回true；如果不可能，则返回false。
所以如果树是这样的：
并且n为11，x为3，则输出将为true，因为第二名玩家可以选择值为2的节点。
为了解决这个问题，我们将遵循以下步骤：
定义一个名为solve()的方法，它将接收节点、x、l和r，l和r最初为false，其作用如下：
如果节点不存在，则返回并退出。
如果l为true，则将leftVal加1；否则，如果r为true，则将rightVal加1。
如果节点值为x，则调用solve(节点的左子节点, x, true, false)和solve(节点的右子节点, x, false, true)。
否则，调用solve(节点的左子节点, x, l, r)和solve(节点的右子节点, x, l, r)。
主方法将如下所示：
nodeToX := 0, leftVal := 0, rightVal := 0
调用solve(根节点, x, false, false)
nodeToX := n – leftVal – rightVal – 1
temp := rightVal, nodeToX和leftVal中的最大值
如果(nodeToX + leftVal + rightVal – (2*temp) >= 0)，则返回false；否则返回true。
示例（Python）
让我们来看下面的实现，以便更好地理解：
class TreeNode: def __init__(self, data, left = None, right = None): self.data = data self.left = left self.right = right def insert(temp,data): que = [] que.append(temp) while (len(que)): temp = que[0] que.pop(0) if (not temp.left): if data is not None: temp.left = TreeNode(data) else: temp.left = TreeNode(0) break else: que.append(temp.left) if (not temp.right): if data is not None: temp.right = TreeNode(data) else: temp.right = TreeNode(0) break else: que.append(temp.right) def make_tree(elements): Tree = TreeNode(elements[0]) for element in elements[1:]: insert(Tree, element) return Tree class Solution(object): def btreeGameWinningMove(self, root, n, x): self.nodeToX = 0 self.leftVal = 0 self.rightVal = 0 self.solve(root,x) self.nodeToX = n - self.leftVal - self.rightVal - 1 temp = max(self.rightVal,max(self.nodeToX,self.leftVal)) return not (self.nodeToX + self.leftVal + self.rightVal - (2*temp)>=0) def solve(self,node,x,l= False,r = False): if not node: return if l: self.leftVal+=1 elif r: self.rightVal+=1 if node.data == x: self.solve(node.left,x,True,False) self.solve(node.right,x,False,True) else: self.solve(node.left,x,l,r) self.solve(node.right,x,l,r) ob = Solution() root = make_tree([1,2,3,4,5,6,7,8,9,10,11]) print(ob.btreeGameWinningMove(root, 11, 3))
输入
[1,2,3,4,5,6,7,8,9,10,11] 11 3
输出
true
363 次浏览
