LeetCode1110-删点成林

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/delete-nodes-and-return-forest/

中文链接：https://leetcode-cn.com/problems/delete-nodes-and-return-forest/

题目详述

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

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

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

示例：

1
2
输入：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、各不相同的值。

题目详解

  • 要解决这个问题，需要解决以下两个关键问题：
    • 删除当前结点要通知它的父结点，即把对应的指针置为 null。
    • 判断当前结点是否为新的根结点，需要让它原来的父结点通知它。
  • 显然这是一个递归过程。在递归调用的过程中，可以通过传参向下通知，通过返回值向上通知。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class LeetCode_01110 {
    
    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
        boolean[] del = new boolean[1001];
        for (int d : to_delete) {
            del[d] = true;
        }
        List<TreeNode> res = new ArrayList<>();
        dfs(root, true, del, res);
        return res;
    }

    private TreeNode dfs(TreeNode root, boolean isRoot, boolean[] del, List<TreeNode> res) {
        if (root == null) {
            return null;
        }
        if (del[root.val]) {
            dfs(root.left, true, del, res);
            dfs(root.right, true, del, res);
            return null;
        } else {
            if (isRoot) {
                res.add(root);
            }
            root.left = dfs(root.left, false, del, res);
            root.right = dfs(root.right, false, del, res);
            return root;
        }
    }
}

上面存在一些重复的代码，可以合并简化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class LeetCode_01110 {

    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
        boolean[] del = new boolean[1001];
        for (int d : to_delete) {
            del[d] = true;
        }
        List<TreeNode> res = new ArrayList<>();
        dfs(root, true, del, res);
        return res;
    }

    private TreeNode dfs(TreeNode root, boolean isRoot, boolean[] del, List<TreeNode> res) {
        if (root == null) {
            return null;
        }
        boolean flag = del[root.val];
        if (!flag && isRoot) {
            res.add(root);
        }
        root.left = dfs(root.left, flag, del, res);
        root.right = dfs(root.right, flag, del, res);
        return flag ? null : root;
    }
}