1ms Java Solution


  • 16
    S
    public int rob(TreeNode root) {
        int[] maxVal = dpRob(root);
        return Math.max(maxVal[0], maxVal[1]);
    }
    
    public int[] dpRob(TreeNode root) {
        if (root == null) {
            return new int[]{0, 0};
        } else {
            int[] maxVal = new int[2];//maxVal[0] store the max value without robing current node, maxVal[1] store the max value with robing current node,
            int[] leftMax = dpRob(root.left);
            int[] rightMax = dpRob(root.right);
            maxVal[0] = Math.max(leftMax[0], leftMax[1]) + Math.max(rightMax[0], rightMax[1]);
            maxVal[1] = leftMax[0] + rightMax[0] + root.val;
            return maxVal;
        }
    }

  • 0
    V

    quite clean and smart


  • 0
    B

    But where do you check the condition that "two directly-linked houses were broken into on the same night"?


  • 1
    S

    when you choose to not rob current node, you can either rob its children or not, so its Math.max(leftMax[0], leftMax[1]) + Math.max(rightMax[0], rightMax[1]);
    when you choose to rob current node, you cannot rob its children, so you can only have this leftMax[0] + rightMax[0] + root.val;


  • 4
    S

    sweet, I did the same approach. :)

    public int rob(TreeNode root) {
        if(root == null) return 0; 
        
        int[] sums = robSubSum(root);
        return Math.max(sums[0], sums[1]); 
    }
    
    private int[] robSubSum(TreeNode root) {
        if(root == null) return new int[]{0,0}; 
        
        int[] leftSum = robSubSum(root.left); 
        int[] rightSum = robSubSum(root.right); 
        
        int[] sums = new int[2]; 
        // case of skip this node 
        sums[0] = Math.max(leftSum[0],leftSum[1]) + Math.max(rightSum[0],rightSum[1]);  
        // case of count this node 
        sums[1] = Math.max(sums[0], root.val + leftSum[0] + rightSum[0]); 
        
        return sums; 
    }

  • 0
    J

    What do leftMax[0] and leftMax[1] mean here? Why do you need to get the greater one from them?


  • 0
    S

    leftVal[0] store the max value without robing current node, leftVal[1] store the max value with robing current node,


  • 0
    W

    I rewrote my solution inspired by your code and posted it in Chinese, hope it will not offend you.


  • 0
    S

    thats alright


  • 0
    2

    @sallycr you should just return sums[1] in rob function.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.