# 1ms Java Solution

• ``````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;
}
}``````

• quite clean and smart

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

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

• 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;
}``````

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

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

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

• thats alright

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

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