Binary Tree Coloring Game: เกมทาสีบน Binary Tree

โจทย์

เกม 2 คนบน Binary Tree (โหนดมีค่า 1..n, n คี่):

1. Player 1 เลือกโหนด x ทาสีแดง
2. Player 2 เลือกโหนด y ≠ x ทาสีน้ำเงิน
3. สลับกันทาสีเพื่อนบ้าน (parent, left, right) ของโหนดสีตัวเองที่ยังไม่ถูกทา
4. ไม่ทาได้ → pass, ทั้งคู่ pass → จบเกม ชนะคนที่ทาสีได้มากกว่า

เราคือ Player 2: หา y ที่รับประกันชนะได้หรือไม่ (return true/false)

ข้อสังเกตสำคัญ (Key Insight)

เมื่อ Player 1 เลือก x ต้นไม้จะถูกแบ่งเป็น 3 ส่วนที่แยกจากกัน (Player 2 สามารถเลือกเข้าครอบครองส่วนใดส่วนหนึ่ง):

1. Left subtree ของ x (ขนาด = left_size)
2. Right subtree ของ x (ขนาด = right_size)
3. ส่วนที่เหลือ (parent side) ขนาด = n - left_size - right_size - 1

Player 2 จะเลือกส่วนที่ใหญ่ที่สุด ถ้าส่วนนั้น > n/2 → Player 2 ชนะแน่นอน

อัลกอริทึม

1. DFS หาโหนด x และคำนวณขนาด left/right subtree
2. คำนวณ parent_size = n - left - right - 1
3. หา max_part = max(left, right, parent_size)
4. ถ้า max_part > n // 2 → return True (Player 2 ชนะได้)

การติดตั้ง (Python Implementation)

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_part = max(self.left_size, self.right_size, parent_size)
        
        return max_part > n // 2

# Helper สร้าง tree จาก 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]
    for i, node in enumerate(nodes):
        if node:
            left_idx = 2*i + 1
            right_idx = 2*i + 2
            if left_idx < len(nodes):
                node.left = nodes[left_idx]
            if right_idx < len(nodes):
                node.right = nodes[right_idx]
    return nodes[0]

# ทดสอบ
#       1
#      / \
#     2   3
#    / \ / \
#   4  5 6  7
#  / \ / \
# 8  9 10 11
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 เลือกโหนด 2 ได้ส่วนซ้ายขนาด 6 > 5.5)

Output

True

การวิเคราะห์ตัวอย่าง

Tree (n=11), x=3 (โหนดค่า 3)
        1
       / \
      2   3  ← x
     / \ / \
    4  5 6  7
   / \ / \
  8  9 10 11

ส่วน 3 ส่วน:
- Left subtree of 3: โหนด 6,7,10,11 → size = 4
- Right subtree of 3: (ไม่มี) → size = 0
- Parent side: โหนด 1,2,4,5,8,9 → size = 6

max_part = 6 > 11//2 = 5.5 → Player 2 เลือกโหนด 2 (parent side) ชนะแน่นอน

Complexity

• Time: O(n) - DFS หนึ่งครั้ง
• Space: O(h) - recursion stack, h = ความสูงต้นไม้

สรุป

โจทย์ดูซับซ้อนแต่ลดรูปได้ง่าย: Player 2 ชนะได้ก็ต่อเมื่อมี "ส่วน" ใดส่วนหนึ่งของต้นไม้ (แบ่งโดย x) มีขนาด > n/2 เพราะ Player 2 จะเข้าครอบครองส่วนนั้นเต็มๆ

หากมีข้อสงสัย สามารถถามได้ในส่วนความคิดเห็นครับ