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