企业官网建设流程全解析

LeetCode-Go 题解 1110：删除节点并返回森林（Delete Nodes And Return Forest）的 Go 实现

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

导读

本文围绕 LeetCode 1110 题「删除节点并返回森林」展开，以 leetcode/1110.Delete-Nodes-And-Return-Forest/README.md 为骨架，深入讲解如何在给定待删除节点值列表的前提下，通过一次 DFS 遍历将二叉树拆分为多棵独立子树，并返回森林中所有树的根节点。读完本文，你将掌握"边遍历边删节点、以返回值判定子树是否被切除"这一经典树形递归技巧，并看到它在 LeetCode-Go 仓库中的完整源码、测试用例与验证方式，可直接复制到本地运行验证。

一、题目描述

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

在删去所有值出现在to_delete数组中的节点后，原来的树会分裂成一片森林（若干棵互不相交的树组成的集合）。

要求返回森林中每棵树的根节点，结果可以按任意顺序返回。

示例 1：

Input: root = [1,2,3,4,5,6,7], to_delete = [3,5] Output: [[1,2,null,4],[6],[7]]

原始树结构如下（层序遍历表示）：

1 / \ 2 3 / \ / \ 4 5 6 7

删除值为3和5的两个节点后：

• 值为1的节点是原根，保留下来，其右孩子3被删除，左子树中5被删除，最终形成[1,2,null,4]这棵树；
• 值为6、7的两个节点原本是3的孩子，3被删除后它们各自成为新树的根，即[6]、[7]。

最终输出[[1,2,null,4],[6],[7]]。

约束条件：

二、题目大意

给出一棵二叉树和一个删除数组，要求删除数组中相同元素值的节点，输出删除后形成的森林。

核心要点有三：

1. 节点值全局唯一，因此可以用哈希表（Go 中为map[int]bool）加速"该节点是否应该被删除"的查找；
2. 删除节点本质上是"剪断"其父节点指向它的指针，被剪断的子树会独立出来成为森林中的一棵树；
3. 需要特殊判断被删除的节点是否是（子树的）根节点：如果当前节点保留且是一棵新树的根，就把它加入结果集；如果当前节点被删除，则其左右孩子可能成为新树的根。

三、解题思路：一次 DFS 边遍历边删除

3.1 整体思路

这是一道简单题（LeetCode 难度分类为 Medium 偏易）。常规做法是：先遍历一遍树，同时检查当前节点的值是否在to_delete中。为了把查找从 O(len(to_delete)) 降到 O(1)，先把to_delete数组中的所有值放进一个map[int]bool中。

遍历过程中需要同时处理两件事：

1. 判断当前节点是否要加入结果集：只有当当前节点保留（不在删除集合中）且它是某棵树的根时，才把它加入结果集；
2. 剪断被删除节点的父子指针：如果一个节点的值在删除集合中，那么它原本的父节点需要把指向它的指针置空，这样它下面的子树才能"脱钩"成独立树。

3.2 关键点：如何判定"根"

这里的难点在于"根"的判定是动态变化的：

• 对整棵原始树而言，root天然是根；
• 一旦某个节点被删除，它的左右孩子就升级为新的根；
• 而一个保留节点的孩子，只有在孩子自己是被删除节点的孩子、或者孩子本身被删除时，其"根"身份才成立。

因此，递归函数需要携带一个isRoot参数向下传递：进入某节点时，isRoot表示"当前节点是否是某棵新树的候选根"。如果isRoot == true且当前节点不在删除集合中，则它就是一棵新树的根，直接加入结果集。

3.3 用返回值向上传递"父指针是否需要剪断"

由于 Go 的递归无法直接修改父节点的Left/Right指针（除非在父节点层面判断），实现上采用了一个很巧妙的约定：递归函数返回一个 bool，表示"当前节点是否已经被删除"。父节点拿到返回值后，如果为true，就把对应的孩子指针置为nil。

综合这两点，就得到了仓库中的核心实现：

func delNodes(root *TreeNode, toDelete []int) []*TreeNode { if root == nil { return nil } res, deleteMap := []*TreeNode{}, map[int]bool{} for _, v := range toDelete { deleteMap[v] = true } dfsDelNodes(root, deleteMap, true, &res) return res } func dfsDelNodes(root *TreeNode, toDel map[int]bool, isRoot bool, res *[]*TreeNode) bool { if root == nil { return false } if isRoot && !toDel[root.Val] { *res = append(*res, root) } isRoot = false if toDel[root.Val] { isRoot = true } if dfsDelNodes(root.Left, toDel, isRoot, res) { root.Left = nil } if dfsDelNodes(root.Right, toDel, isRoot, res) { root.Right = nil } return isRoot }

四、逐步推演：递归函数的执行过程

以上实现出自 leetcode/1110.Delete-Nodes-And-Return-Forest/1110. Delete Nodes And Return Forest.go，下面逐行拆解其执行逻辑。

4.1 入口函数 delNodes

1. 若root == nil（空树），直接返回nil；
2. 初始化结果切片res与哈希表deleteMap；
3. 遍历toDelete，把每个值写入deleteMap（map[int]bool的键查找平均 O(1)）；
4. 调用dfsDelNodes(root, deleteMap, true, &res)：注意第三个参数传入true，表示原始根节点天然是候选根；
5. 返回res。

4.2 递归函数 dfsDelNodes 的四个分支

递归函数签名中：

• root：当前访问节点；
• toDel：删除集合哈希表；
• isRoot：当前节点是否为"新树的候选根"；
• res：结果集指针（切片通过指针传递，保证跨递归层级追加有效）。

函数体逻辑：

分支 1：空节点终止

if root == nil { return false }

空节点不算被删除，返回false，父节点无需剪断指针。

分支 2：作为新树根入结果集

if isRoot && !toDel[root.Val] { *res = append(*res, root) }

当前节点是候选根且不在删除集合中，说明它是一棵保留树的根，加入结果集。注意这里先判断再修改 isRoot，顺序很关键。

分支 3：根据是否被删除，更新传给孩子的 isRoot

isRoot = false if toDel[root.Val] { isRoot = true }

先默认孩子不是根；但如果当前节点在删除集合中，那么它的左右孩子就升级为新的候选根，isRoot置为true后传给两个孩子。

分支 4：剪断被删除的孩子

if dfsDelNodes(root.Left, toDel, isRoot, res) { root.Left = nil } if dfsDelNodes(root.Right, toDel, isRoot, res) { root.Right = nil } return isRoot

先递归处理左、右子树，然后利用返回值判断：如果孩子节点被删除（返回true），就把root.Left或root.Right置为nil，完成"剪断"。最后，return isRoot把"当前节点是否被删除"的信息返回给父节点，供父节点决定是否剪断指向本节点的指针。

4.3 用示例数据手动验证

以root = [1,2,3,4,5,6,7]，to_delete = [3,5]为例：

最终结果集为[[1,2,null,4],[6],[7]]，与题目示例输出一致。注意2的左孩子5被剪断后，2的 Left 为nil，因此树1表示为[1,2,null,4]。

4.4 时间复杂度与空间复杂度

• 时间复杂度 O(n)：每个节点恰好被访问一次；每次"是否删除"的判断是哈希表 O(1) 查找，其中 n 为节点总数（≤ 1000）；
• 空间复杂度 O(n)：递归深度在最坏情况下为树高（极端退化为链时可达 n）；此外还需 O(len(to_delete)) 的哈希表空间和结果集空间。

五、测试用例与运行验证

5.1 仓库中的测试用例

对应测试文件位于 leetcode/1110.Delete-Nodes-And-Return-Forest/1110. Delete Nodes And Return Forest_test.go，共覆盖 3 组场景：

qs := []question1110{ { para1110{[]int{1, 2, 3, 4, 5, 6, 7}, []int{3, 5}}, ans1110{[][]int{{1, 2, structures.NULL, 4}, {6}, {7}}}, }, { para1110{[]int{1, 2, 4, 2}, []int{2}}, ans1110{[][]int{{1}}}, }, { para1110{[]int{}, []int{1}}, ans1110{[][]int{}}, }, }

三组用例分别验证了：

1. 典型场景：删除两个中间节点，森林中产生 3 棵树（含根、含叶子节点各自成树）；
2. 根被删除的退化场景：root = [1,2,4,2]，to_delete = [2]。注意该输入中出现了重复值2（测试数据构造并不严格满足"值互异"约束），由于删的是值为 2 的节点，最终只剩节点1一棵树[[1]]，同时验证了"根节点值不在删除集合时正常保留"；
3. 空树边界：root = []，to_delete = [1]，期望结果为空森林[][]int{}，对应delNodes中root == nil直接返回nil的分支。

测试函数通过structures.Ints2TreeNode把层序数组还原成二叉树，再调用delNodes得到森林，与期望答案比对。

5.2 本地运行测试

本仓库在 structures/TreeNode.go 中提供了完整的二叉树工具链：TreeNode结构体、NULL = -1 << 63空节点占位常量、Ints2TreeNode(ints []int) *TreeNode（按层序数组还原树）、Tree2ints（把树还原回层序数组）等，测试数据正是借助这些工具构造与断言的。

在仓库根目录执行：

go test -v ./leetcode/1110.Delete-Nodes-And-Return-Forest/

即可看到该用例组的运行输出：

------------------------Leetcode Problem 1110------------------------ 【input】:{[1 2 3 4 5 6 7] [3 5]} 【output】:... 【input】:{[1 2 4 2] [2]} 【output】:... 【input】:{[] [1]} 【output】:...

仓库根目录的 gotest.sh 还提供了全量测试脚本，使用go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...一次性对全部题解生成覆盖率报告（本仓库整体覆盖率目标为 100%），可以借此验证本题及其余题解的回归状态。

六、边界情况与扩展思考

6.1 需要注意的边界情况

1. 空树：root == nil时直接返回nil，测试用例 3 覆盖；
2. 根节点被删除：原始根一旦被删除，整棵树会被切分为其左右子树森林，此时delNodes传入的初始isRoot = true在根节点处被重置为false后再传给孩子，孩子因isRoot = true而各自入结果集；
3. 叶子节点被删除：叶子被删除时没有孩子，isRoot置 true 后传给nil子树，不产生任何新树，仅把true返回给父节点完成剪断；
4. to_delete中出现树中不存在的值：哈希表查找不会命中，对该节点无影响，代码天然兼容；
5. to_delete为空：deleteMap为空，所有节点都不命中删除分支，原始根以isRoot = true入结果集，最终返回[整棵树]，即"不删除任何节点"的退化情况。

6.2 两种实现风格对比

本题还有一种常见写法：后序遍历中先递归处理左右子树、再处理当前节点（自底向上），删除节点时直接返回nil给父节点以完成剪断。而本仓库采用的方案是先序式"标记 + 返回值"：通过isRoot参数向下传递"根身份"，通过返回值向上传递"是否剪断"。两者本质等价，本方案的优点是：

• 入结果集与剪断逻辑分层清晰，isRoot与返回值职责单一；
• 不需要显式区分左右子树的处理顺序，代码更简洁。

6.3 可迁移性

dfsDelNodes这种"一个 bool 参数向下传状态、一个 bool 返回值向上传剪断信号"的递归模式，在大量"删除树节点并重组"类问题（如修剪二叉搜索树、删除子树统计等）中均可复用，是树形递归中值得固化的通用范式。

七、小结

LeetCode 1110 的核心不复杂：用哈希表加速删除判定，用一次 DFS 同时完成"收集新树根"与"剪断被删节点指针"两件事。仓库实现通过isRoot参数与 bool 返回值的巧妙配合，将"删除后哪些节点成为新树根"的问题化解为递归中自然的父子信息传递，配合 测试文件 中的三组用例，可以完整验证包括空树、根节点被删在内的全部关键路径。掌握这一模式，你对树形结构的递归设计与信息传递会有更深的体会。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go