1ms Java Solution

  • 16
    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

    quite clean and smart

  • 0

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

  • 1

    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

    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

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

  • 0

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

  • 0

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

  • 0

    thats alright

  • 0

    @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.