Tree Heist
MediumTrees
Problem
The houses of a gated community are wired as a binary tree, each holding some cash (node.val). The alarm goes off if two houses joined by a direct parent-child link are both robbed on the same night.
Given the root, return the most cash that can be taken without triggering the alarm.
Example 1
- Input:
- root = [3, 2, 3, null, 3, null, 1]
- Output:
- 7
Rob the root (3) and the two grandchildren (3 and 1).
Example 2
- Input:
- root = [3, 4, 5, 1, 3, null, 1]
- Output:
- 9
Rob the two children: 4 + 5.
Constraints
- 0 ≤ number of nodes ≤ 10^4
- Tree height ≤ 500
- 0 ≤ node.val ≤ 10^4
Hint
Show the first hint
Robbing a node forbids its children but not its grandchildren. What does a parent need to know about each child?
Walkthrough
How to approach it
01Clarify before coding
- Are values non-negative? Yes, so robbing nothing is never better than some choice.
- Is only parent-child adjacency forbidden? Yes; siblings and grandparent-grandchild are fine.
- Empty tree? 0.
02Brute force
Try every subset of houses with no parent-child pair, or recurse 'rob or skip' at each node without memoisation.
Cost: Exponential: the plain recursion re-solves the same grandchild subtrees again and again.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.