JAVA | DFS + DP + Greedy | 100% |
\nclass Solution {\n    //these are the vals of the left and right node of x\n    public int left = -1, right = -1;\n    public boolean btreeGameWinningMove(Tre
```\nclass Solution {\n    //these are the vals of the left and right node of x\n    public int left = -1, right = -1;\n    public boolean btreeGameWinningMove(TreeNode root, int n, int x) {\n        //strategy: DFS + DP + Greedy\n        //try to block the 3 neighbors that player 1 chooses\n        //dp[i] means all of the nodes below node i and itself\n        int[] dp = new int[n + 1];\n        dfs(root, dp, x);\n        //figure out the amt of nodes in the left and right node of x\n        left = (left == -1) ? 0 : dp[left];\n        right = (right == -1) ? 0 : dp[right];\n        //the amt of nodes for the parent of x is just the remaining nodes that are not left or right or x\n        //if any of these amt are more than half then choose that node and we win\n        return Math.max(left, Math.max(right, n - left - right - 1)) > n / 2;\n    }\n    private int dfs(TreeNode root, int[] dp, int x) {\n        //reached end \n        if (root == null) {\n            return 0;\n        }\n        //seen before so use that amt\n        if (dp[root.val] != 0) {\n            return dp[root.val];\n        }\n        if (root.val == x) {\n            //find the left and right val of node x\n            left = (root.left != null) ? root.left.val : -1;\n            right = (root.right != null) ? root.right.val : -1;\n        }\n        //total nodes are all the nodes to left and right and itself\n        return dp[root.val] = dfs(root.left, dp, x) + dfs(root.right, dp, x) + 1;\n    }\n}\n```
[]