[Java/C++/Python] Simple recursion and Follow-Up
Intuition\nThe first player colors a node,\nthere are at most 3 nodes connected to this node.\nIts left, its right and its parent.\nTake this 3 nodes as the roo
# **Intuition**\nThe first player colors a node,\nthere are at most 3 nodes connected to this node.\nIts left, its right and its parent.\nTake this 3 nodes as the root of 3 subtrees.\n\nThe second player just color any one root,\nand the whole subtree will be his.\nAnd this is also all he can take,\nsince he cannot cross the node of the first player.\n<br>\n\n# **Explanation**\n`count` will recursively count the number of nodes,\nin the left and in the right.\n`n - left - right` will be the number of nodes in the "subtree" of parent.\nNow we just need to compare `max(left, right, parent)` and `n / 2`\n<br>\n\n# **Complexity**\nTime `O(N)`\nSpace `O(height)` for recursion\n<br>\n\n**Java:**\n```java\n    int left, right, val;\n    public boolean btreeGameWinningMove(TreeNode root, int n, int x) {\n        val = x;\n        count(root);\n        return Math.max(Math.max(left, right), n - left - right - 1) > n / 2;\n    }\n\n    private int count(TreeNode node) {\n        if (node == null) return 0;\n        int l = count(node.left), r = count(node.right);\n        if (node.val == val) {\n            left = l;\n            right = r;\n        }\n        return l + r + 1;\n    }\n```\n\n**C++:**\n```cpp\n    int left, right, val;\n    bool btreeGameWinningMove(TreeNode* root, int n, int x) {\n        val = x, n = count(root);\n        return max(max(left, right), n - left - right - 1) > n / 2;\n    }\n\n    int count(TreeNode* node) {\n        if (!node) return 0;\n        int l = count(node->left), r = count(node->right);\n        if (node->val == val)\n            left = l, right = r;\n        return l + r + 1;\n    }\n```\n\n**Python:**\n```python\n    def btreeGameWinningMove(self, root, n, x):\n        c = [0, 0]\n        def count(node):\n            if not node: return 0\n            l, r = count(node.left), count(node.right)\n            if node.val == x:\n                c[0], c[1] = l, r\n            return l + r + 1\n        return count(root) / 2 < max(max(c), n - sum(c) - 1)\n```\n\n# **Fun Moment of Follow-up**:\nAlex and Lee are going to play this turned based game.\nAlex draw the whole tree. `root` and `n` will be given.\nNote the `n` will be odd, so no tie in the end.\n\nNow Lee says that, this time he wants to color the node first.\n1. Return `true` if Lee can ensure his win, otherwise return `false`\n\n2. Could you find the set all the nodes,\nthat Lee can ensure he wins the game?\nReturn the size of this set.\n\n3. What is the complexity of your solution?\n\n\n# Solution to the follow up 1\n\nYes, similar to the solution [877. Stone Game](https://leetcode.com/problems/stone-game/discuss/154610/DP-or-Just-return-true)\nJust return true.\nBut this time, Lee\'s turn to ride shotgun today! Bravo.\n\n**Java/C++**\n```java\n    return true;\n```\n**Python:**\n```python\n    return True\n```\n\n# Solution to the follow up 2\nThere will one and only one node in the tree,\nthat can Lee\'s win.\n\n**Java/C++**\n```java\n    return 1\n```\n**Python:**\n```python\n    return 1\n```\n\n# Solution to the follow up 3\nIt can be solve in `O(N)`.\n
[]