# 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:**

![](https://assets.leetcode.com/uploads/2019/07/01/screen-shot-2019-07-01-at-53836-pm.png)

```
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。

```java
/**
 * 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;
    }

}
```
