Split a Tree by Removing Values

A company org chart is a binary tree with distinct employee ids. Some employees leave: their ids are listed in to_delete. Removing a node also cuts it away from its children, so each remaining child becomes the root of its own tree. Return a list of the roots of all trees that remain, in any order.

Examples

       1
      / \
     2   3
    / \ / \
   4  5 6  7

Input:  root = build_tree([1, 2, 3, 4, 5, 6, 7]), to_delete = [3, 5]
Output: [tree_to_list(t) for t in ...] == [[1, 2, None, 4], [6], [7]]

Input:  root = build_tree([1, 2]), to_delete = [1]
Output: [[2]]

Constraints

• 0 <= number of nodes <= 1000
• All node values are distinct; to_delete contains distinct values that may or may not be in the tree

Goals

• Collect new roots that appear when a parent is deleted
• Use the return value of the recursion to detach removed nodes