simple JAVA O(n) solution with explanation
Given a red node the best chance we can win is to blue-color its parent or either of its children.\nWhy?\nBecause by doing so we block the first player in one o
Given a red node the best chance we can win is to blue-color its parent or either of its children.\nWhy?\nBecause by doing so we block the first player in one of the three directions. We hence take all the rest of the nodes as our own. \nAny other options can\'t beat these three. A simple proof of condradiction can prove this arguement.\n\nSo we simply calculate the score in the three scenerios and check if any of them can win.\n```\nclass Solution {\n    public boolean btreeGameWinningMove(TreeNode root, int n, int x) {\n        TreeNode red = find(root, x);\n        int leftNum = count(red.left);\n        int rightNum = count(red.right);\n        int parentNum = n - leftNum - rightNum - 1;\n        if(leftNum > n - leftNum || rightNum > n - rightNum || parentNum > n - parentNum) {\n            return true;\n        } else {\n            return false;\n        }\n    }\n    private TreeNode find(TreeNode root, int x) {\n        if(root == null) {\n            return null;\n        }\n        if(root.val == x) {\n            return root;\n        } else {\n            TreeNode left = find(root.left, x);\n            TreeNode right = find(root.right, x);\n            if(left != null) {\n                return left;\n            }\n            if(right != null) {\n                return right;\n            }\n            return null;\n        }\n    }\n    private int count(TreeNode red) {\n        if(red == null) {\n            return 0;\n        }\n        return 1 + count(red.left) + count(red.right);\n    }\n}\n```
[]