Tree DP
Compute each node's value from its children's values in postorder.
Tree DP: Pick nodes, none adjacent, maximise the sum
20 is a leaf. Taken, it is worth 20. Skipped, 0. Both go up, because the parent will decide which one it can use.
Cost
- Best
- O(n)
- Average
- O(n)
- Worst
- O(n)
- Space
- O(h)