House Robber III
Medium · Trees · Dynamic Programming · Tree · Depth-First Search · Binary Tree
Problem
The houses in a neighborhood form a binary tree: root is the entrance, and every house other than the root has exactly one parent house. Each node’s value is the money in that house.
An alarm goes off if two directly linked houses (a parent and its child) are both robbed on the same night.
Return the most money that can be robbed without setting off the alarm.
Examples
Input: root = [4,1,6,3,2,null,1] Output: 11
Robbing 3, 2 and 6 gives 11. Taking the root instead allows at most 4 + 3 + 2 + 1 = 10.
Input: root = [2,9,null,1,1] Output: 9
House 9 alone beats 2 + 1 + 1 = 4.
Input: root = [3,2,3,null,3,null,1] Output: 7
The root and the two grandchildren: 3 + 3 + 1.
Constraints
- The number of nodes is in the range [1, 10^4]
- 0 <= Node.val <= 10^4
Approaches
- Rob or skip, recomputed without memo — time exponential in the height, space O(h) for the recursion
Follow-up
What if the alarm also connected grandparents to grandchildren, so no two robbed houses may be within two links of each other? Return three numbers per node instead of two: robbed, not robbed but a child robbed, and neither. Each state lists which states its children may be in, and the pass stays O(n).
Related problems
Start free on Cariara · Coding problems · System design studio
