#337
House Robber III
Medium DP on trees
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Houses form a binary tree; robbing two directly linked houses triggers the alarm. Return the most money you can rob.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: rob a tree of houses without robbing a parent and its child.
Why this works: each node returns two numbers: best if robbed, best if skipped. The parent combines them.
Example: 3 (2 (-, 3), 3 (-, 1))
rob root + grandchildren: 3 + 3 + 1 = 7✦Hints open one at a time
For each node return two numbers: best if you rob it, best if you don't.
Rob node → children must be skipped. Skip node → each child can be robbed or not, whichever is better.
↗Approach
Postorder DFS returning {robbed, skipped}. robbed = val + left.skipped + right.skipped; skipped = max(left) + max(right).
</>Solution (Java)
/**
* class TreeNode { int val; TreeNode left, right; } // provided by LeetCode
*/
class Solution {
public int rob(TreeNode root) {
int[] r = dfs(root);
return Math.max(r[0], r[1]);
}
// returns {best if this node is robbed, best if it is not}
private int[] dfs(TreeNode n) {
if (n == null) return new int[]{0, 0};
int[] l = dfs(n.left), r = dfs(n.right);
int robbed = n.val + l[1] + r[1];
int skipped = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
return new int[]{robbed, skipped};
}
}!Common mistake
Plain recursion that tries grandchildren directly without returning both states — exponential.
Complexity
- Time: O(n).
- Space: O(h).
Topic: Dynamic Programming
🎬 Episodes 86–96: video coming soon