Houses form a binary tree; each TreeNode holds the amount of money in that house (TreeNode(val, left=None, right=None) is in the starter). The alarm goes off if two houses joined by an edge (a parent and its child) are both robbed.
Write rob(root: TreeNode | None) -> int: the most money you can take without setting off the alarm. An empty tree gives 0.
Examples:
4
/ \
1 2
/ \
3 5
rob(root) == 12: take 4, 3 and 5. They are never parent and child (3 and 5 are grandchildren of 4).
- A single house worth
9gives9. - A chain
1 -> 10 -> 1(each the left child of the previous) gives10, which beats1 + 1.
Constraints: up to about 130,000 nodes, values 0..10**4, tree depth stays small (it's balanced in the big test).
Aim for O(n). Recomputing the same subtrees again and again (for example, recursing into grandchildren separately) is exponential and times out.
Show hint
The answer for a subtree depends on whether its root is robbed. What if each call reported the best total for both cases?