Binary Tree Coloring Game: Chiến Thuật Thắng Cuộc Trên Cây Nhị Phân

Đề bài: 2 người chơi tô màu trên cây nhị phân n node (n lẻ, giá trị 1..n). Player 1 chọn x (tô đỏ), Player 2 chọn y ≠ x (tô xanh). Luân phiên tô màu neighbor (cha/con) chưa tô. Ai tô nhiều node hơn thắng. Player 2 có thể chọn y để đảm bảo thắng không?

Phân tích chiến lược

Khi Player 1 chọn x, cây bị chia thành 3 vùng:

1. Cây con trái của x (size = left)
2. Cây con phải của x (size = right)
3. Phần còn lại (cha và các nhánh khác) = parent = n - left - right - 1

Player 2 nên chọn y là gốc của vùng lớn nhất trong 3 vùng trên. Khi đó Player 2 kiểm soát toàn bộ vùng đó, Player 1 chỉ có 2 vùng còn lại. Player 2 thắng nếu: max(left, right, parent) > n/2.

Code Python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def btreeGameWinningMove(self, root: TreeNode, n: int, x: int) -> bool:
        self.left_size = 0
        self.right_size = 0
        
        def dfs(node):
            if not node:
                return 0
            left = dfs(node.left)
            right = dfs(node.right)
            if node.val == x:
                self.left_size = left
                self.right_size = right
            return left + right + 1
        
        dfs(root)
        parent_size = n - self.left_size - self.right_size - 1
        max_region = max(self.left_size, self.right_size, parent_size)
        
        return max_region > n // 2

# Helper: build tree từ list level-order
def build_tree(vals):
    if not vals: return None
    nodes = [TreeNode(v) if v is not None else None for v in vals]
    kids = nodes[::-1]
    root = kids.pop()
    for node in nodes:
        if node:
            if kids: node.left = kids.pop()
            if kids: node.right = kids.pop()
    return root

# Test: cây từ hình vẽ, n=11, x=3
root = build_tree([1,2,3,4,5,6,7,8,9,10,11])
ob = Solution()
print(ob.btreeGameWinningMove(root, 11, 3))  # True (Player 2 chọn node 2)

Giải thích test case

Cây: 1
/ \
2 3 (x)
/ \ / \
4 5 6 7
/ \ / \
8 9 10 11

• left(3) = 2 (node 6,7)
• right(3) = 2 (node 6,7? wait - sửa: left subtree của 3 là 6, right là 7 → size=1+1=2? Actually node 6,7 là leaves → left_size=1, right_size=1)
• parent = 11 - 1 - 1 - 1 = 8 (node 1,2,4,5,8,9,10,11)
• max = 8 > 11/2 = 5.5 → True

Kết luận

Player 2 thắng bằng cách chiếm vùng lớn nhất. Chỉ cần 1 DFS tính size 3 vùng. O(n) time, O(h) space.