simple python dfs beats 98% solution
We first build a undirectd acyclic graph \nAs player 1 choose a node first, the only chance for player 2 to win is to choose a children of node with value x , w
***We first build a undirectd acyclic graph \n*As player 1 choose a node first, the only chance for player 2 to win is to choose a children of node with value x , which are \'chances\' . We always choose node next to player 1\'s node, major reason is only \none edge between 2 nodes, this act like a \'separator\'.\n We know that n is always odd, as if n is even, player 2 always can win, as player 2 can choose a neighbour node which partites the graph into equal number of nodes (at minimum), and player 1 will always run out of node first \n We hope the number of nodes in the sub tree, \'chances\', at least greater than (n-1)/2 in order to win player 1.\n Choosing the closest neighbour node to player 1 node in a tree always guarantee to maximize your chance of winning***\n\n```\n\nclass Solution:\n    def build_graph(self,rt,parent):\n        if rt:\n            if parent:\n                self.graph[rt.val].add(parent.val)\n            if rt.left:\n                self.graph[rt.val].add(rt.left.val)\n            if rt.right:\n                self.graph[rt.val].add(rt.right.val)\n            self.build_graph(rt.left,rt)\n            self.build_graph(rt.right,rt)\n        return \n            \n    def dfs_node(self,node,visited):\n        if node:\n            visited.add(node)\n            nc = 1\n            for neighbour in self.graph[node]:\n                if neighbour not in visited:\n                    nc += self.dfs_node(neighbour,visited)\n            return nc\n        else:\n            return 0\n        \n    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n        self.graph = defaultdict(lambda:set())\n        self.build_graph(root,None)\n        for chances in self.graph[x]:\n            node_counts = self.dfs_node(chances,set([x]))\n            if  node_counts > (n-1)/2:\n                return True\n        return False
[]