Binary Tree Coloring Game

Problem Id: 1145 Difficulty: Medium Tag: Tree Tag: Depth-first Search


Intuition

Removing any edge in a tree would split the graph into at most 2 parts.

The chosen node would split the graph into at most 3 parts, the optimize solution is to choose one of the neighbours of the chosen node. And after player 2 choose this node, the graph would be sliptted into 2 parts. Each player could only fill node in one of the part.

So, if player 2 could choose one node and his part has more node than others, he could win.

So we solve this problem by count the number of nodes in left sub-tree, right sub-tree of the chosen node. If max(number of left, number of right, number of others) is greater than half of all the nodes, player II could win.

Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def btreeGameWinningMove(self, root: TreeNode, n: int, x: int) -> bool:
        self.result = None
        self._dfs(root, x, n)
        return self.result

    def _dfs(self, node, x, n):
        if node is None:
            return 0
        l = self._dfs(node.left, x, n)
        r = self._dfs(node.right, x, n)
        if node.val == x:
            if l > n // 2 or r > n // 2 or (n - l - r - 1) > n // 2:
                self.result = True
            else:
                self.result = False
        return l + r + 1