LeetCode 1110. 删点成林

约 5 分钟
文章信息 7 个分类 5 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节 亚马逊
标签
数组 哈希表 深度优先搜索 树 二叉树

题目描述

✅ 1110. 删点成林

image-20260928225751417

image-20260928225751418

题意分析

删除值在 to_delete 中的节点及它们相连的边，返回剩余各棵树的根，顺序不限。节点值互不相同，所以用值集合就能判断哪个节点需要删除。

一个保留节点成为森林中的根，当且仅当它原本就是整棵树的根，或者它的父节点被删除。要让父节点决定保留连接还是登记新根，必须先知道孩子处理后是否还存在，因此使用后序遍历。

解法：后序 DFS

核心思路

[!blue]

dfs(node) 返回处理后仍能连接到父节点的子树根；如果 node 本身被删除，就返回空。递归中已经从这棵子树断开的其他树根，则加入 res，不再通过返回值连接回去。

先递归处理左右孩子，并将返回值赋回 node.left、node.right。这样需要删除的孩子已经变为空，保留的孩子也已完成内部清理。若当前节点保留，直接返回它，父子关系继续存在。

若当前节点被删除，清理后仍非空的左右孩子都会失去父节点，应分别登记为新树根，再向上一层返回空以断开当前节点。父子都被删除时，孩子递归会先登记自己的保留后代，并返回空；当前节点因此不会再次登记这些后代，也不会把待删除的孩子加入结果。

每个非原根节点仅由自己的父节点负责登记，条件恰好是“自己保留、父节点被删”，所以不重不漏。原根没有父节点，入口再检查最终返回值，非空就补入 res。所有节点都被删除时结果自然为空，没有节点被删除时只返回原树根。

解题步骤

  • 把待删值存入集合。
  • 递归清理并重新赋值左右指针。
  • 被删节点登记非空孩子并返回空，否则返回自身。
  • 最后处理保留的原根。

代码实现

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
}

复杂度分析

设节点数为 $n$，删除列表长度为 $d$，树高为 $h$。

  • 时间复杂度：期望 $O(n+d)$。建集合需要 $O(d)$，每个节点只访问一次，集合查询的期望时间为 $O(1)$。
  • 空间复杂度：$O(d+h)$，不计输出，包含删除集合与递归栈；退化为链时 $h=n$。

关键点总结

[!green]

  • 递归返回值直接决定父节点应保留的连接。
  • 只删除指定节点，其后代可能分别留下成为新树。
  • 当前实现会重接原树指针；Go 需要向调用方传播追加后的结果切片头部，不只是在发生扩容时才需要。

易错点总结

[!yellow]

  • 调用孩子递归却不接收返回值，父节点仍连着被删节点。
  • 把所有保留节点都登记，会把同一棵树拆成重复结果。
  • 左右孩子登记用互斥分支，会遗漏其中一棵树。

相似题目

题目 难度 关联与区别
814. 二叉树剪枝 中等 原题删除整棵不合格子树，本题只删指定节点，下面未删的孩子可能成为森林新根。
450. 删除二叉搜索树中的节点 中等 BST删除通常重接成一棵树，本题删除后保留多个根，不应强行把各子树接回一起。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/81195471
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！