Robbing the tree
Choose the nodes of a tree with the largest total value so that no two chosen nodes are parent and child, by returning two numbers from each subtree. About 20 minutes.
Two answers per node
You may pick nodes, but never a parent together with one of its children. For each node, you need two answers about its subtree: the best total if this node is picked, and the best total if it is not.
The two answers differ in what they allow the children to do, so a single number is not enough information for the parent.
take = house + skip_a + skip_b skip = max(a, b)
- leaves
- 1: (1, 0) 2: (2, 0)
The leaves 1 and 2: take is their value, skip is 0.
Combine the children
If you take the node, both children must be skipped, so add the node's value to the children's skip answers.
If you skip the node, each child is free: use the better of its take and skip answers, and add the two. An empty subtree has take and skip both zero. The answer for the whole tree is the better of the root's two numbers.
best = max(take, skip)
A node is taken. What happens to its children?
- AThey must be skipped, so only their skip answers are used
- BThey choose freely
- CThey must be taken too
Show the answer
They must be skipped, so only their skip answers are used. A parent and its child may not both be picked.
House robber on a tree
Thieves find a neighbourhood whose houses form a binary tree, the root being the entrance. Each house holds an amount of money. If two directly linked houses (a parent and its child) are both robbed, the alarm sounds. Given the root, return the largest total that can be robbed without setting off the alarm.
root = [3, 2, 3, null, 3, null, 1] → 7
0 ≤ number of nodes ≤ 10,000 · 0 ≤ node.val ≤ 10,000