1145. Binary Tree Coloring Game

Link

Solution

player2 下一個選項其實只有三種， x(player1選的node) 的parent or left or right。

只要任何一個所造成的count > n/2，那player2肯定能贏。

其中拿parent的狀態是，player2 拿到n - left - right -1 的node數。

DFS設計思路

1. 推演

• 子問題的答案 (return value)

2. 結算

    int left = 0, right = 0;
    public boolean btreeGameWinningMove(TreeNode root, int n, int x) {
        
        dfs(root, x);        
        int parent = n - right - left - 1;
        
        if(right > n/2 || left > n/2 || parent > n/2) return true;
        return false;
        
    }
    

    
    public int dfs(TreeNode node, int x){
        if(node == null){
            return 0;
        }
        int l = dfs(node.left, x);
        int r = dfs(node.right, x);
        if(node.val == x){
            left = l;
            right = r;
        }
       
        return l + r + 1;
    }