1110. 删点成林 (opens new window)

1.DFS

当前节点在删除节点列表时，除了要删除该节点与孩子节点的关联之外，还需要删除该节点与父节点之间的关联。因此搜索时当前节点删除不了父节点关联，需要交给父节点进行删除(每个节点都要判断子节点是否在删除列表当中)。另外搜索时，无论当前节点是否在删除列表当中，都需要递归搜索左右子树所有节点。

另外搜索过程中，虽然不能判断一个节点是否是非删除子树的根节点，但是加入的非删除子树根节点一定满足一条性质：它的父亲一定在删除队列当中。

• 如果当前节点不在删除队列，①遍历左右子树②删除左右子树关联
• 当前节点在删除队列，①删除左右子树关联②遍历左右子树③如果左右子树不在删除列表，则加入结果集中。

class Solution {
    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
            List<Integer> list=new ArrayList<>();
            List<TreeNode> res=new ArrayList<>();
            for(int i:to_delete)
            list.add(i);
            if(!list.contains(root.val)) res.add(root);
            dfs(res,list,root);
            return res;
    }
    public void dfs(List<TreeNode> res,List<Integer> list,TreeNode root){
        if(root==null) return ;
        if(!list.contains(root.val)){
            dfs(res,list,root.left);
            dfs(res,list,root.right);
            if(root.left!=null&&list.contains(root.left.val)) root.left=null;
            if(root.right!=null&&list.contains(root.right.val)) root.right=null;
        }else{
            if(root.left!=null){
                TreeNode leftchild=root.left;
                root.left=null;
                if(!list.contains(leftchild.val)) res.add(leftchild);
                dfs(res,list,leftchild);

            }
            if(root.right!=null){
                TreeNode rightchild=root.right;
                root.right=null;
                if(!list.contains(rightchild.val))res.add(rightchild);
                dfs(res,list,rightchild);

            }
        }
    }
}