java recursion O(n) time O(h) space, beats 100%
\n/*\nthe problem is same as seeing if can count # of nodes from x.left, or x.right, or x.parent, such that we can count # of nodes, ycount, such that ycount > 
```\n/*\nthe problem is same as seeing if can count # of nodes from x.left, or x.right, or x.parent, such that we can count # of nodes, ycount, such that ycount > n - ycount\n\nthe reason for this intuition is that any node acts as a path block, meaning we pick any node i, then depends on the opponent node j, either left subtree, right subtree or the parent subtree of i will be a path block\n\nalgorithm: it\'s simply a variation of count # nodes in a given tree\n1. locate node with value x\n    *if root.val == x, we can only split tree into left, or right. so no need to count parent tree\n2. count nodes in x.left, x.right, x.parent respectively\n3. validate if any ycount > n - ycount, or equivalently, 2*ycount > n\n\ntime: O(n)\nspcae: O(height) for recursion stack\n*/\nclass Solution {\n    public boolean btreeGameWinningMove(TreeNode root, int n, int x) {\n        if (root == null) {\n            return true;\n        }\n        \n        if (root.val == x) {\n            return (2 * count(root.left, -1) > n) || (2 * count(root.right, -1) > n); \n        }\n        \n        //root is not x\n        TreeNode xnode = locate(root, x);\n        int nparent = count(root, x);\n        if (2 * nparent > n) {\n            return true;\n        }\n        int nleft = count(xnode.left, -1);\n        if (2 * nleft > n) {\n            return true;\n        }\n        int nright = count(xnode.right, -1);\n        if (2 * nright > n) {\n            return true;\n        }\n        return false;\n    }\n    //count # of nodes, if meet t, return. t is the node where we should stop counting that subtree, node t should not be counted either\n    public int count(TreeNode root, int t) {\n        if (root == null || root.val == t) {\n            return 0;\n        }\n        int left = count(root.left, t);\n        int right = count(root.right, t);\n        return left + right + 1;\n    }\n    //return target node x, given root node\n    public TreeNode locate(TreeNode root, int x) {\n        if (root == null || root.val == x) {\n            return root;\n        }\n        TreeNode left = locate(root.left, x);\n        if (left != null) {\n            return left;\n        }\n        TreeNode right = locate(root.right, x);\n        return right;\n    }\n    \n}\n```
[]