LeetCode 1110. 删点成林

2022-05-17 HGNULB 约 11 分钟

文章信息 7 个分类 5 个标签

分类

题目描述

✅ 1110. 删点成林

题意分析

给一棵二叉树和一组待删除的值 to_delete，把所有值在这组里的节点从树上抹掉。一个节点被抹掉后，它原本挂着的左右子树就失去了父亲，各自成为独立的一棵树。最终要返回剩下的所有树的根节点，顺序任意。题目保证节点值互不相同，所以「值」和「节点」是一一对应的，判断某节点是否要删只看它的值就够了。

从要求里能读出两个信号。第一，答案是「根节点的集合」，而一个节点成为根，当且仅当它自己不被删除、且它的父亲被删除（或者它本来就是整棵树的根且自己不被删）。这句话把问题从「怎么删」转成了「谁会变成根」，判定只依赖当前节点和它父亲两层信息，是局部可判的。第二，删除一个节点会影响它与父亲之间的那条边，也会影响它与两个孩子之间的边，也就是说每个节点的处理都需要知道孩子被处理后的结果，这天然是自底向上的顺序。

边界要留意几处：整棵树的根本身可能在删除列表里，此时它的两个孩子（若非空）成为新的根，而它自己不进结果；被删节点的孩子可能为空，空孩子不能加入结果集，否则答案里会混进空树；被删节点的孩子自己也可能要被删，此时它同样不该进结果，而它的孩子才是新根，说明判定必须在孩子处理完之后再做；to_delete 可能覆盖所有节点，此时结果是空列表。

解法：后序 DFS

核心思路

先想最直白的做法：遍历一遍找到所有待删节点，逐个从树里摘掉，把它的孩子登记为新根。问题立刻来了——如果一个待删节点的孩子也是待删节点，我们刚把它登记成根，转头又要把它删掉，还得从结果里撤销；如果处理顺序是自顶向下，父亲被删时孩子还没处理，此时孩子的子树形态还没定下来，登记的是一棵「尚未清理干净」的树。瓶颈就在这里：自顶向下的顺序让「当前节点的归属」依赖于尚未确定的下游状态，于是不得不反复修补。

关键观察是把处理顺序倒过来。若先把左右子树彻底处理完，再看当前节点，那么当前节点的两个孩子指针指向的一定是已经清理完毕的合法子树，此时只需回答一个问题：当前节点自己是否被删？如果不删，它应该继续挂在父亲底下，于是把自己交还给父亲；如果要删，它的两个孩子（已清理过、非空的那些）就是新的森林根，登记进结果，然后告诉父亲「这里空了」。

于是递归函数的契约可以显式写成：dfs(node) 先递归处理并重挂左右孩子，然后返回「node 这棵子树处理完后应该挂在父亲位置上的那个节点」——node 不被删就返回 node 本身，node 被删就返回空，同时把它非空的左右孩子加入结果集。这个返回值的语义是整个解法的不变量：父亲拿到什么就直接赋给自己的孩子指针，不需要任何额外判断。而 res 的不变量是：任何时刻 res 里的节点都是「已确定不被删、且父亲已被删」的节点，唯独整棵树的原根没有父亲，需要在递归返回后单独补一次判断。

解题步骤

第一步把 to_delete 灌进哈希集合。原因是删除判定会在每个节点上执行一次，若直接线性扫数组，总代价变成节点数乘以删除列表长度；换成集合后单次判定摊销到常数，整体才是线性。

第二步进入递归，出口是节点为空直接返回空。这条出口同时承担两个职责：一是终止递归，二是让「空孩子」这个情况自然地把空值传回给父亲，父亲赋值后孩子指针仍是空，语义一致。

第三步是先递归后处理的顺序，也就是 node.left = dfs(node.left) 与 node.right = dfs(node.right) 必须写在删除判定之前。这两行不只是「递归下去」，赋值本身就是重挂动作：孩子若被删，返回的空值会当场把这条边断开，使得后面读取 node.left 时看到的是清理后的真实状态。少了赋值，边永远断不掉，被删的节点还会挂在树上被输出。

第四步是当前节点的判定。若不在删除集合里，直接返回它自己，把决定权交还给父亲——注意此时不能把它加入 res，因为它是否成为根取决于父亲的命运，而父亲的信息在这一层是看不到的，登记工作必须由父亲来做。若在删除集合里，则依次检查左右孩子是否非空，非空的加入 res，最后返回空。这里检查非空是必要的，因为空孩子不构成一棵树。

第五步是收尾。递归对原根返回后，若返回值非空说明原根没被删，它自己就是一棵树的根，但它没有父亲替它登记，所以要在外层手动加入 res；若返回空说明原根被删，它的孩子已在递归内部登记过了，无需额外处理。

以完全二叉树 root = [1,2,3,4,5,6,7]（根 1，左 2 右 3，2 的孩子是 4 和 5，3 的孩子是 6 和 7）、to_delete = [3,5] 走一遍。集合是 {3,5}。递归从 1 进入，先下到 2，再下到 4：4 的左右都是空，返回空后 4 的两个指针保持空，4 不在集合里，返回 4 自身，于是 2.left = 4。接着处理 5：5 的孩子都空，5 在集合里，左右孩子均为空所以什么都不加，返回空，于是 2.right = null——这条赋值就是断边动作，5 从此不在树上。回到 2，2 不在集合里，返回 2 自身，于是 1.left = 2，此时以 2 为根的子树是「2 挂着 4」。再走右边，先下到 6：不在集合，返回 6，3.left = 6；再到 7：不在集合，返回 7，3.right = 7。回到 3，3 在集合里，左孩子 6 非空加入 res，右孩子 7 非空加入 res，返回空，于是 1.right = null。最后回到 1，1 不在集合里，返回 1。外层看到返回值非空，把 1 加入 res。最终 res 是 [6, 7, 1]，对应三棵树 [6]、[7]、[1,2,null,4]，与期望一致。可以留意 5 的处理：它被删且孩子全空，所以它对结果的贡献是纯粹的「断边」，这正是先递归后判定才能干净处理的情形。

代码实现

class Solution {
    // 后序遍历适合先清理左右子树，再决定当前节点是否要断开与父节点的连接。
    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
        Set<Integer> deleted = new HashSet<>();
        for (int val : to_delete) {
            deleted.add(val);
        }

        List<TreeNode> res = new ArrayList<>();
        TreeNode newRoot = dfs(root, deleted, res);
        if (newRoot != null) {
            res.add(newRoot);
        }

        return res;
    }

    private TreeNode dfs(TreeNode node, Set<Integer> deleted, List<TreeNode> res) {
        if (node == null) {
            return null;
        }

        node.left = dfs(node.left, deleted, res);
        node.right = dfs(node.right, deleted, res);

        if (!deleted.contains(node.val)) {
            return node;
        }
        if (node.left != null) {
            res.add(node.left);
        }
        if (node.right != null) {
            res.add(node.right);
        }

        return null;
    }
}

func delNodes(root *TreeNode, toDelete []int) []*TreeNode {
    // 后序遍历适合先清理左右子树，再决定当前节点是否要断开与父节点的连接。
    deleted := make(map[int]bool, len(toDelete))
    for _, val := range toDelete {
        deleted[val] = true
    }

    res := make([]*TreeNode, 0)
    newRoot := dfs(root, deleted, &res)
    if newRoot != nil {
        res = append(res, newRoot)
    }

    return res
}

func dfs(node *TreeNode, deleted map[int]bool, res *[]*TreeNode) *TreeNode {
    if node == nil {
        return nil
    }

    node.Left = dfs(node.Left, deleted, res)
    node.Right = dfs(node.Right, deleted, res)

    if !deleted[node.Val] {
        return node
    }
    if node.Left != nil {
        *res = append(*res, node.Left)
    }
    if node.Right != nil {
        *res = append(*res, node.Right)
    }

    return nil
}

复杂度分析

时间复杂度：$O(n + d)$，其中 n 表示节点数，d 表示待删除节点数量。建集合是 $O(d)$，递归对每个节点恰好访问一次，每次只做一次哈希查询和常数次指针赋值，因此遍历部分是 $O(n)$。

空间复杂度：$O(n)$，哈希集合占 $O(d)$，递归栈深度等于树高，最坏情况下树退化成链时为 $O(n)$，结果列表最多容纳 $O(n)$ 个根，三项合计仍是 $O(n)$。

关键点总结

树上的删除、剪枝、重构类问题，统一用「递归函数返回处理后的新子树根，父亲用返回值覆盖自己的孩子指针」这一契约。断边这个动作因此被 node.left = dfs(node.left) 这一行赋值自动完成，不需要维护父指针，也不需要额外的删除函数。

后序的必要性来自依赖方向：当前节点的决策需要孩子已被清理，而孩子的决策不需要知道父亲的结论（父亲只负责登记），所以自底向上恰好满足全部依赖。面试时能说清「为什么必须是后序而不是先序」，比写对代码更能体现理解深度。

职责划分要干净：节点自己只回答「我留不留」，「我是不是新根」由父亲来判断和登记。把这两件事混在一层写，就会陷入「先登记再撤销」的泥潭。

根节点没有父亲，因此所有依赖父亲的登记逻辑都要在递归外补一次特判。这是树递归题的通用盲点，凡是「由父亲决定孩子命运」的写法都要检查根这一条。

把待删值放进哈希集合，是把「每次判定 $O(d)$」降到「$O(1)$」的标准动作。这个改写在任何「集合成员判定出现在循环内层」的场景都适用。

结果只收集非空孩子。空指针不是一棵树，这条检查看似琐碎，却是本题唯一需要显式写出的空值过滤，遗漏后返回的森林里会混入无效项。

易错点总结

错误写法：把递归写成 dfs(node.left, ...) 而不赋值回 node.left。用例 root = [1,2,3]、to_delete = [2] → 2 虽然进了递归也被判为删除，但 1 的左指针仍指向 2，返回的树 [1,2,3] 里被删节点还在，答案错误。

错误写法：把删除判定写在递归孩子之前（先序）。用例 root = [1,2,null,3]、to_delete = [2,3] → 处理 2 时孩子还没清理，此时把非空的 3 登记为新根，可 3 自己也要删，结果里混进了本该消失的 3。

错误写法：当前节点不删时就把它加入 res。用例 root = [1,2,3]、to_delete = [] → 1、2、3 全被登记，返回三棵树，而正确答案只有原树一棵。

错误写法：忘记在递归外对原根补一次登记。用例 root = [1]、to_delete = [2] → 1 不被删也没有父亲替它登记，返回空列表而非 [[1]]。

错误写法：原根被删时又在外层无条件把返回值加入 res。用例 root = [1,2,3]、to_delete = [1] → 递归返回空，若不判空直接 add，结果列表里会多出一个 null，判题报错。

错误写法：登记孩子时不检查是否为空。用例 root = [1,2]、to_delete = [1] → 右孩子为空却被加入结果，返回 [[2], null]，多出一个空树。

错误写法：用数组线性查找代替哈希集合判定。用例 n 为 1000、to_delete 长度 1000 → 逻辑虽对但退化成百万次比较，在更大数据下会明显变慢，且丢掉了面试官想看的复杂度意识。

错误写法：删除节点后返回 node 而不是空。用例 root = [1,2,3]、to_delete = [2] → 父亲拿到 2 又挂回去，等于没删，同时 2 的孩子还被登记进了结果，出现节点重复出现在两棵树里。

错误写法：只登记左孩子，用 else 把右孩子的登记挡掉。用例 root = [1,2,3]、to_delete = [1] → 只有 2 进结果，3 整棵子树凭空消失，返回 [[2]] 而非 [[2],[3]]。

错误写法：Go 里把 res 按值传成 []*TreeNode 而非指针。用例任意含删除节点的树 → 函数内 append 触发扩容后写入的是副本，外层 res 收不到任何登记，返回结果缺失全部新根。

相似题目

题目	难度	考察点
814. 二叉树剪枝	中等	同为后序返回新根，但删除条件依赖子树聚合结果而非节点自身取值
LCR 047. 二叉树剪枝	中等	上题的同题异号版本，可用来验证自己写的后序模板是否真正通用
450. 删除二叉搜索树中的节点	中等	删除后必须保持 BST 性质，需要找前驱或后继来顶替，删法复杂得多
669. 修剪二叉搜索树	中等	借助 BST 有序性可整棵子树跳过，返回的是孩子而非空
226. 翻转二叉树	简单	同样靠返回值重挂指针，但修改的是左右顺序，不涉及节点消失
617. 合并二叉树	简单	递归同时下钻两棵树，返回值语义从「保留谁」变成「合成谁」
543. 二叉树的直径	简单	后序返回的是深度这一数值而非节点，答案靠全局变量在递归中更新
236. 二叉树的最近公共祖先	中等	返回值编码的是「子树里找到了谁」，靠左右都非空定位分叉点
1123. 最深叶节点的最近公共祖先	中等	需要同时返回深度和节点两份信息，是单返回值契约的自然升级
112. 路径总和	简单	自顶向下传递累加值，与本题自底向上的信息流方向恰好相反
297. 二叉树的序列化与反序列化	困难	递归重建树时同样用返回值挂接子树，考的是遍历序与结构的对应关系