Python 3 | DFS | One pass & Three pass | Explanation
Intuition\n- When first player chose a node x, then there are 3 branches left there for second player to choose (left subtree of x, right subtree of x, parent e
### Intuition\n- When first player chose a node `x`, then there are 3 branches left there for second player to choose (left subtree of `x`, right subtree of `x`, parent end of `x`. \n- For the second player, to ensure a win, we need to make sure that there is one branch that dominate the sum of the other 2 branches. As showed at below.\n\t- left + right < parent\n\t- parent + right < left\n\t- parent + left < right\n### Three-pass solution\n```\nclass Solution:\n    def btreeGameWinningMove(self, root: TreeNode, n: int, x: int) -> bool:\n        first = None\n        def count(node):\n            nonlocal first\n            total = 0\n            if node: \n                if node.val == x: first = node\n                total += count(node.left) + count(node.right) + 1\n            return total\n        \n        s = count(root) # Get total number of nodes, and x node (first player\'s choice)\n        l = count(first.left) # Number of nodes on left branch \n        r = count(first.right) # Number of nodes on right branch \n        p = s-l-r-1 # Number of nodes on parent branch (anything else other than node, left subtree of node or right subtree of node)\n        return l+r < p or l+p < r or r+p < l\n```\n\n### One-pass solution\n- Once you understand the idea of three-pass solution, it\'s pretty easy to modify the code to a one-pass solution\n```\nclass Solution:\n    def btreeGameWinningMove(self, root: TreeNode, n: int, x: int) -> bool:\n        l = r = 0\n        def count(node):\n            nonlocal l, r\n            total = 0\n            if node: \n                l_count, r_count = count(node.left), count(node.right)\n                if node.val == x: \n                    l, r = l_count, r_count\n                total += l_count + r_count + 1\n            return total\n        s = count(root) \n        p = s-l-r-1 \n        return l+r < p or l+p < r or r+p < l\n```
['Depth-First Search', 'Python', 'Python3']