資料結構
網路
關係資料庫管理系統 (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 次瀏覽
