Python, DFS
Intuition\nWe have 3 different ways to choose the element that will beat opponent.\n1. Choose left sub-tree of opponent node\n2. Choose right sub-tree of oppone
# Intuition\nWe have 3 different ways to choose the element that will beat opponent.\n1. Choose left sub-tree of opponent node\n2. Choose right sub-tree of opponent node\n3. Choose parent of opponent node\n\nThen we should calculate amount of nodes in left and right sub-trees. If one of them grater than sum of others - we can win.\n\nAnother edge case when opponent choose root. In this case we can win only if amount of left and right sub-trees are different.\n\n# Complexity\n- Time complexity:\nO(N)\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 btreeGameWinningMove(self, root, n: int, x: int) -> bool:\n\n        def calculateNodes(node):\n            if not node:\n                return 0\n            \n            result = 1\n            \n            if node.left:\n                result += calculateNodes(node.left)\n            if node.right:\n                result += calculateNodes(node.right)\n\n            return result\n\n        if root.val == x:\n            return calculateNodes(root.left) != calculateNodes(root.right)\n\n        def dfs(node):\n            if node.val == x:\n                a = calculateNodes(node.left)\n                b = calculateNodes(node.right)\n                c = n - (a + b + 1)\n\n                return a > b + c or b > a + c or c > a + b\n\n            if node.left:\n                result = dfs(node.left)\n                if result != None:\n                    return result\n            if node.right:\n                result = dfs(node.right)\n                if result != None:\n                    return result\n\n            return None\n\n        return dfs(root)\n```
['Python3']