House Robber III
Problem
root, return the maximum amount that can be stolen.[3,2,3,null,3,null,1]Output7 (3+3+1)[3,4,5,1,3,null,1]Output9 (4+5)1 ≤ n ≤ 104 · 0 ≤ Node.val ≤ 104
Try it yourself
class Solution {
public int rob(TreeNode root) {
}
}
Instinct A node's best answer depends only on its children's answers - post-order DFS that returns a tiny tuple of states per node.
Memory hack Kids report up, parent decides - every subtree hands its parent a small report card, and the parent never re-reads the kids' homework.
Open the Tree & Graph DP guide →Approaches
Brute ForceRob-or-Skip Recursion
O(n·φh)Space O(h)rob(node) = max(val + rob(4 grandchildren), rob(left) + rob(right)).
Every node is re-solved from both its parent and its grandparent, so the call count
grows like Fibonacci in the depth (φ ≈ 1.618) — exponential on a skewed
tree.
public int rob(TreeNode root) { if (root == null) return 0; int take = root.val; if (root.left != null) take += rob(root.left.left) + rob(root.left.right); if (root.right != null) take += rob(root.right.left) + rob(root.right.right); int skip = rob(root.left) + rob(root.right); return Math.max(take, skip); }
Captures the recurrence, but recomputes the same subtrees exponentially often.
BetterMemoization (HashMap per Node)
O(n)Space O(n)The answer for a subtree never changes, so cache rob(node) in a
HashMap<TreeNode, Integer>. Each node is computed once; later calls
from the grandparent are O(1) lookups.
private final Map<TreeNode, Integer> memo = new HashMap<>(); public int rob(TreeNode root) { if (root == null) return 0; Integer cached = memo.get(root); if (cached != null) return cached; int take = root.val; if (root.left != null) take += rob(root.left.left) + rob(root.left.right); if (root.right != null) take += rob(root.right.left) + rob(root.right.right); int best = Math.max(take, rob(root.left) + rob(root.right)); memo.put(root, best); return best; }
Linear time, but pays for a hash map with n entries.
OptimalPost-Order DP Returning {rob, skip}
O(n)Space O(h)Return a pair per node: robThis = val + l.skip + r.skip and
skipThis = max(l) + max(r). The grandchildren are already folded into the
children's skip values, so each node is visited exactly once and no map
is needed.
public int rob(TreeNode root) { int[] r = dfs(root); return Math.max(r[0], r[1]); } private int[] dfs(TreeNode node) { // {best if node robbed, best if node skipped} if (node == null) return new int[2]; int[] l = dfs(node.left), r = dfs(node.right); int robThis = node.val + l[1] + r[1]; int skipThis = Math.max(l[0], l[1]) + Math.max(r[0], r[1]); return new int[]{robThis, skipThis}; }
One pass, only the recursion stack — the standard answer.
(take, skip) pair replaces the prev1/prev2 variables.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Rob-or-Skip Recursion | O(n·φh) | O(h) |
| Better | Memoization (HashMap per Node) | O(n) | O(n) |
| Optimal | Post-Order DP Returning {rob, skip} | O(n) | O(h) |
- Assuming it is “rob alternate levels” — skipping two levels in a row can be optimal.
- When skipping a node, forcing children to be robbed — each child must take
max(rob, skip). - Forgetting null checks before reaching grandchildren in the recursive version.
- Write the take/skip recurrence first; it drives all three versions.
- Point out the overlap: a grandchild is solved from both its parent and grandparent.
- Explain why returning a pair removes the need for memoization.