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.
# 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