Giả sử có hai người chơi chơi trò chơi theo lượt trên cây nhị phân. Chúng ta có gốc của cây nhị phân này và số nút n trong cây. Ở đây n là số lẻ, và mỗi nút có một giá trị khác biệt từ 1 đến n. Lúc đầu, người chơi thứ nhất đặt tên giá trị x với 1 <=x <=n, và người chơi thứ hai đặt tên giá trị y với 1 <=y <=n và điều đó có một điều kiện, sao cho y! =X. Người chơi đầu tiên tô màu nút bằng giá trị x màu đỏ và người chơi thứ hai tô màu nút bằng giá trị y màu xanh lam. Sau đó, các người chơi lần lượt xuất phát với người chơi đầu tiên. Trong mỗi lượt, người chơi lấy một nút có màu của họ (màu đỏ cho người chơi 1, màu xanh lam cho người chơi 2) và tô màu cho một hàng xóm chưa được tô màu của nút đã chọn (hoặc nút con bên trái hoặc phải, hoặc nút cha của nút được lấy.). Nếu và chỉ khi một người chơi không thể lấy một nút như vậy theo cách này, họ phải vượt qua lượt của mình. Nếu cả hai người chơi vượt qua lượt của họ, trò chơi sẽ kết thúc và người chiến thắng là người chơi tô nhiều nút hơn.
Giả sử chúng ta là người chơi thứ hai. Nếu có thể chọn một y như vậy để đảm bảo chúng ta thắng trò chơi, hãy trả về true. Nếu không thể, hãy trả về false.
Vì vậy, nếu cây như -
và n là 11 và x là 3, thì kết quả đầu ra sẽ là true, vì người chơi thứ hai có thể lấy nút có giá trị 2
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một phương thức có tên là giải quyết (), phương thức này sẽ nhận nút, x, l và r, l và r ban đầu là sai, điều này sẽ hoạt động như bên dưới -
-
nếu nút không có, hãy quay lại và thoát
-
nếu l là true thì tăng leftVal lên 1, ngược lại khi r là true thì tăng rightVal lên 1
-
nếu giá trị của nút là x, thì gọi giải quyết (bên trái của nút, x, đúng, sai) và gọi giải quyết (bên phải của nút, x, sai, đúng)
-
nếu không thì gọi giải quyết (bên trái của nút, x, l, r) và gọi giải quyết (bên phải của nút, x, l, r)
-
Phương thức chính sẽ giống như -
-
nodeToX:=0, leftVal:=0, rightVal:=0
-
gọi giải quyết (root, x, false, false)
-
nodeToX:=n - leftVal - rightVal - 1
-
temp:=tối đa của rightVal, nodeToX và leftVal
-
trả về false nếu (nodeToX + leftVal + rightVal - (2 * temp)> =0), ngược lại là true
Ví dụ (Python)
Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -
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))
Đầu vào
[1,2,3,4,5,6,7,8,9,10,11] 11 3
Đầu ra
true