A tree of rooms is searched for a marker value. Remove every subtree that contains no node with the marker value, so that every remaining node has the marker somewhere in its subtree (itself included). Return the root of what is left, or None if the marker does not occur at all.
Examples
3
/ \
7 3
/ \ / \
7 7 7 3
Input: root = build_tree([3, 7, 3, 7, 7, 7, 3]), marker = 3
Output: tree_to_list(...) == [3, None, 3, None, 3]
Input: root = build_tree([7, 7]), marker = 3
Output: []
Constraints
0 <= number of nodes <= 1000-100 <= node.val, marker <= 100
Goals
- Decide whether to keep a subtree only after both children have been processed
- Return the (possibly new) child pointer from the recursion instead of mutating from above