Problem statement

https://leetcode.com/problems/binary-tree-coloring-game/

Solution

We need to see all subtree we will have if we delete node x. Then the second player must choose the biggest subtree, also he can take it all and he can not takre more. So, run dfs to create tree in defaultdict way, then run dfs once again, calculating number of nodes.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def btreeGameWinningMove(self, root, n, x):
        G = defaultdict(list)
        def dfs(node, par):
            if par:
                x, y = node.val, par.val
                G[x] += [y]
                G[y] += [x]
            if node.left:  dfs(node.left, node)
            if node.right: dfs(node.right, node)
            
        dfs(root, None)
        
        @lru_cache(None)
        def dfs2(node, par):
            ans = 1
            for child in G[node]:
                if child == par: continue
                ans += dfs2(child, node)
            return ans
            
            
        arr = [dfs2(y, x) for y in G[x]]
        return max(arr) * 2 > n