1110. Delete Nodes And Return Forest

Given the root of a binary tree, each node in the tree has a distinct value.

After deleting all nodes with a value in to_delete, we are left with a forest (a disjoint union of trees).

Return the roots of the trees in the remaining forest. You may return the result in any order.

Example 1:

Input: root = [1,2,3,4,5,6,7], to_delete = [3,5]
Output: [[1,2,null,4],[6],[7]]

Constraints:

• The number of nodes in the given tree is at most 1000.

• Each node has a distinct value between 1 and 1000.

• to_delete.length <= 1000

• to_delete contains distinct values between 1 and 1000.

解题要点：

使用递归的方式，先把待delete的数组转换为set，以方便检测。如果是root而且不在delete set里，则加进最终list；继续执行左右child node；最后如果是delete的node，return null；如不是，return当前node。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    List<TreeNode> lst = new ArrayList<>();
    Set<Integer> set = new HashSet<>();
    
    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
        for(int i : to_delete){
            set.add(i);
        }
        root = delete(root, true);   
        return lst;
    }
    private TreeNode delete(TreeNode node, boolean isRoot) {
        if(node == null) return null;
        
        boolean delete = set.contains(node.val);
        if(isRoot && !delete) lst.add(node);
        
        node.left = delete(node.left, delete);
        node.right = delete(node.right, delete);

        return delete ? null : node;
    }

}