House Robber III
Solve this Problemvalues, plus each node's left and right child index (or -1 for no child) — with the root always at index 0.
At any node there are exactly two live possibilities: rob it (its children are off-limits, but its grandchildren aren't) or skip it (its children are free to be robbed or not, independently). Solving that naively re-derives the same subtree's answer over and over from different angles. The fix is to have every node hand back both of its own answers at once — best-if-robbed and best-if-skipped — computed bottom-up from its children's own pairs. A node's robbed value only needs its children's skipped values; its skipped value takes whichever of each child's two values is larger. One pass, root to leaves and back, settles the whole tree.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ values.length ≤ 100 (number of nodes; 0 means an empty tree) - ◆
0 ≤ values[i] ≤ 10000 - ◆
left[i] and right[i] hold the index of that node's left/right child, or -1 if it has none - ◆
the tree's root is always at index 0 when values is non-empty
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Recursive Without Memoization
BruteAt every node, there are exactly two options: rob it (then skip both of its children entirely, but its grandchildren are still fair game), or skip it (then its two children are independently free to be robbed or not). Recursing both ways and taking the better result is correct, but the same node ends up having its best value recomputed from scratch through many different call paths — once as someone's "skipped child," again as someone else's "grandchild still in play" — so the work roughly doubles with every extra level.
O(2ⁿ)O(n)1class Solution {
2 private int[] values, left, right;
3
4 public int robTree(int[] values, int[] left, int[] right) {
5 this.values = values;
6 this.left = left;
7 this.right = right;
8 if (values.length == 0) return 0;
9 return rob(0);
10 }
11
12 private int rob(int idx) {
13 if (idx == -1) return 0;
14 int withNode = values[idx];
15 withNode += grandchildrenSum(idx);
16 int withoutNode = rob(left[idx]) + rob(right[idx]);
17 return Math.max(withNode, withoutNode);
18 }
19
20 private int grandchildrenSum(int idx) {
21 int sum = 0;
22 int l = left[idx], r = right[idx];
23 if (l != -1) sum += rob(left[l]) + rob(right[l]);
24 if (r != -1) sum += rob(left[r]) + rob(right[r]);
25 return sum;
26 }
27}Optimal — Post-Order DP Returning a (Rob, Skip) Pair
OptimalInstead of asking "what's the best answer here" once and recomputing it under different assumptions later, have every node hand back both answers at once — the best total if this node is robbed, and the best total if it isn't. A node's "robbed" value only needs its children's "not robbed" values (since it can't rob a robbed child); a node's "not robbed" value takes whichever of its children's two answers is bigger, independently for each side. Every node is visited exactly once, from the leaves up.
O(n)O(h)1class Solution {
2 private int[] values, left, right;
3
4 public int robTree(int[] values, int[] left, int[] right) {
5 this.values = values;
6 this.left = left;
7 this.right = right;
8 if (values.length == 0) return 0;
9 int[] result = dfs(0);
10 return Math.max(result[0], result[1]);
11 }
12
13 private int[] dfs(int idx) {
14 if (idx == -1) return new int[]{0, 0};
15 int[] leftPair = dfs(left[idx]);
16 int[] rightPair = dfs(right[idx]);
17 int withNode = values[idx] + leftPair[1] + rightPair[1];
18 int withoutNode = Math.max(leftPair[0], leftPair[1]) + Math.max(rightPair[0], rightPair[1]);
19 return new int[]{withNode, withoutNode};
20 }
21}