1145.md

1145. Binary Tree Coloring Game

Solution 1 (time O(n), space O(n))

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def btreeGameWinningMove(self, root, n, x):
        """
        :type root: TreeNode
        :type n: int
        :type x: int
        :rtype: bool
        """
        self.cur_node = None

        def dfs(root):
            if root is None:
                return
            if root.val == x:
                self.cur_node = root
            dfs(root.left)
            dfs(root.right)

        def count(root):
            if root is None:
                return 0
            return 1 + count(root.left) + count(root.right)

        dfs(root)
        t1 = count(self.cur_node.left)
        t2 = count(self.cur_node.right)
        return max(t1, t2, n - 1 - t1 - t2) * 2 > n