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;
}
}
1ms Java Solution


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