# 1110. Delete Nodes And Return Forest
###### tags: `Leetcode` `FaceBook` `DFS`
Link: https://leetcode.com/problems/delete-nodes-and-return-forest/
## 思路
DFS, 如果一个node是要被删除的node，就说明它们的children都要变成head，所以递归的参数isRoot变成true，否则isRoot就是false

对于一个node，
如果isRoot是true，并且之后不需要被删除的话，那么这个node就要被加在ans里面，形成一个新的subtree，然后继续递归它的child，isRoot参数为false
如果isRoot是false，之后还要被删除的话 isRoot参数为true
不管这个node是不是新的root，只要这个node需要被删除，就回传null，这样他的上一层就会连null，而不是这个node

## Code

class Solution {
    Set<Integer> delNum;
    List<TreeNode> ans;
    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
        ans = new ArrayList<>();
        delNum = new HashSet<>();
        for(int i = 0;i < to_delete.length;i++){
            delNum.add(to_delete[i]);
        }
        delete(root, true);
        return ans;
    }
    public TreeNode delete(TreeNode root, boolean isRoot){
        if(root == null) return null;
        boolean deleted = delNum.contains(root.val);
        if(isRoot && !deleted){
            ans.add(root);
        }
        root.left = delete(root.left, deleted);
        root.right = delete(root.right, deleted);
        return deleted?null:root;
    }
}