A greenhouse is built as a binary tree of rooms: each room connects by a door to its parent room and to up to two child rooms. A heater placed in a room warms that room, its parent and its children, and nothing else.
Given the root of the tree (a TreeNode; the values do not matter), write
fewest_heaters(root) returning the smallest number of heaters that warms every room.
An empty greenhouse needs 0.
Examples
Input: root = [1, 2, 3, 4, 5, 6, 7]
Output: 2
Explanation: heaters in rooms 2 and 3 warm all seven rooms.
Input: root = [1, 2, null, 3, null, 4]
Output: 2
Explanation: a chain 1 - 2 - 3 - 4; heaters in 2 and 3 (1 and 3 also works).
Input: root = [9]
Output: 1
(Trees are shown in level order, null marking a missing child.)
Constraints
0 <= number of rooms <= 40000- the tree height is at most 500
Goals
- Return several answers from each subtree, one per situation the parent might need
- Combine the children's answers so that at least one child supplies a heater when required
- Avoid trying every set of rooms, which is exponential