918. Delete Node and Return Forest

Given the root of a binary tree with distinct values and a list of values to delete, remove every node whose value is in the list. The remaining nodes form a forest (a set of disjoint trees). Return the values of the roots of that forest, sorted in ascending order. The input gives a level-order tree array and the delete list separated by ' | '.

Input: A level-order tree array and a JSON list of values to delete, separated by ' | '.

Output: Array — the forest root values, sorted.

Examples

Input: [1,2,3,4,5,6,7] | [3,5]
Output: [1,6,7]
Explanation: Removing 3 exposes 6 and 7; 5 is a leaf, so roots are 1, 6, 7.

Input: [1,2,3] | [1]
Output: [2,3]
Explanation: Deleting the root splits the tree.

Input: [1] | [1]
Output: []
Explanation: Deleting the only node leaves no forest.

Constraints

• 1<=nodes<=1000
• values distinct
• delete list values valid

Asked by