LeetCode刷题【1110】删点成林

给出二叉树的根节点 root，树上每个节点都有一个不同的值。

如果节点值在 to_delete 中出现，我们就把该节点从树上删去，最后得到一个森林（一些不相交的树构成的集合）。

返回森林中的每棵树。你可以按任意顺序组织答案。

示例：

输入：root = [1,2,3,4,5,6,7], to_delete = [3,5]
输出：[[1,2,null,4],[6],[7]]

提示：

• 树中的节点数最大为 1000。
• 每个节点都有一个介于 1 到 1000 之间的值，且各不相同。
• to_delete.length <= 1000
• to_delete 包含一些从 1 到 1000、各不相同的值。

题解

二叉树搜索删除对应节点，看到题目第一反应应该是：因为提供的删除集合是个数组集合，所以先把to_delete转换成hashset，转换成hash查找提供的删除节点

然后就是遍历各个节点找到要删除的节点。删除的节点需要把左右子树放入返回集合中，但是需要判断左右子树的根节点是不是需要删除的节点，如果是则不放入结果结合。

另外还有一个要点，遍历最后需要把删除的节点删除掉

class Solution {

    Set<Integer> deleteSet = new HashSet<>();
    List<TreeNode> list = new ArrayList<>();
    public List<TreeNode> delNodes(TreeNode root, int[] toDelete) {
        for (int i : toDelete) {
            deleteSet.add(i);
        }
        if (!ifDelete(root.val )){
            list.add(root);
        }
        collectDfs(root);
        return list;
    }


    public void collectDfs(TreeNode root){
        if (root == null){
            return;
        }
        TreeNode left = root.left;
        TreeNode right = root.right;
        if (ifDelete(root.val)){
            root = null;
            if (left !=null && !ifDelete(left.val)){
                list.add(left);
            }
            if (right !=null && !ifDelete(right.val)){
                list.add(right);
            }
        }
        collectDfs(left);
        collectDfs(right);
        if (root==null)return;
        if (root.left != null && ifDelete(root.left.val)){
            root.left = null;
        }
        if (root.right != null && ifDelete(root.right.val)){
            root.right = null;
        }
    }


    public boolean ifDelete(int val){
        return deleteSet.contains(val);
    }
}

其实本来一开始并不是这么写的，本来写了两次dfs，第一次会把删除的节点的值标记成-1，第二次dfs的时候根据节点值为-1来判断，但是实际跑出来效果速度不行。还是就整合起来一次dfs搞定