PYTHON SOL | LINEAR TIME | EXPLAINED WITH PICTURE | EASY | TRAVERSING |
TIME AND SPACE COMPLEXITY\nRuntime: 36 ms, faster than 89.14% of Python3 online submissions for Binary Tree Coloring Game.\nMemory Usage: 14 MB, less than 52.72
# TIME AND SPACE COMPLEXITY\nRuntime: 36 ms, faster than 89.14% of Python3 online submissions for Binary Tree Coloring Game.\nMemory Usage: 14 MB, less than 52.72% of Python3 online submissions for Binary Tree Coloring Game.\n\n\n# EXPLANATION\n![image](https://assets.leetcode.com/users/images/f35b2647-dd8a-4280-bfa2-9e31f2bdab0f_1656850678.351904.png)\n\n# CODE\n```\n# Definition for a binary tree node.\n# class TreeNode:\n#     def __init__(self, val=0, left=None, right=None):\n#         self.val = val\n#         self.left = left\n#         self.right = right\nclass Solution:\n    def findParent(self,node,par = None):\n        if node:\n            self.parent[node.val] = par\n            self.findParent(node.left,node)\n            self.findParent(node.right,node)\n    \n    def traverse(self,node,done):\n        if node:\n            if node in done: return 0\n            done[node] = True\n            a = self.traverse(self.parent[node.val],done)\n            b = self.traverse(node.left,done)\n            c = self.traverse(node.right,done)\n            return a + b + c + 1\n        return 0\n    \n    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n        self.parent = {}\n        self.findParent(root)\n        parent = self.parent[x]\n        node = root if root.val == x else parent.left if parent and parent.left and parent.left.val == x else parent.right\n        up = self.traverse(parent,{node:True})\n        left = self.traverse(node.left,{node:True})\n        right = self.traverse(node.right,{node:True})\n        return (up > left + right) or (left > up + right) or (right > up + left)\n```\n
['Depth-First Search', 'Python', 'Python3']