尧图网页设计 
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数组中的节点后原来的树会分裂成一片森林若干棵互不相交的树组成的集合。要求返回森林中每棵树的根节点结果可以按任意顺序返回。示例 1Input: 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]]。约束条件约束项范围树中节点数最多1000个节点值介于1到1000之间且各不相同to_delete.length最多1000to_delete中的值介于1到1000各不相同二、题目大意给出一棵二叉树和一个删除数组要求删除数组中相同元素值的节点输出删除后形成的森林。核心要点有三节点值全局唯一因此可以用哈希表Go 中为map[int]bool加速该节点是否应该被删除的查找删除节点本质上是剪断其父节点指向它的指针被剪断的子树会独立出来成为森林中的一棵树需要特殊判断被删除的节点是否是子树的根节点如果当前节点保留且是一棵新树的根就把它加入结果集如果当前节点被删除则其左右孩子可能成为新树的根。三、解题思路一次 DFS 边遍历边删除3.1 整体思路这是一道简单题LeetCode 难度分类为 Medium 偏易。常规做法是先遍历一遍树同时检查当前节点的值是否在to_delete中。为了把查找从 O(len(to_delete)) 降到 O(1)先把to_delete数组中的所有值放进一个map[int]bool中。遍历过程中需要同时处理两件事判断当前节点是否要加入结果集只有当当前节点保留不在删除集合中且它是某棵树的根时才把它加入结果集剪断被删除节点的父子指针如果一个节点的值在删除集合中那么它原本的父节点需要把指向它的指针置空这样它下面的子树才能脱钩成独立树。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若root nil空树直接返回nil初始化结果切片res与哈希表deleteMap遍历toDelete把每个值写入deleteMapmap[int]bool的键查找平均 O(1)调用dfsDelNodes(root, deleteMap, true, res)注意第三个参数传入true表示原始根节点天然是候选根返回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根据是否被删除更新传给孩子的 isRootisRoot 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]为例节点值在删除集合isRoot 传入值动作返回值1否true原始根加入结果集[1]isRoot 保持 false 传给孩子false保留2否false不入结果集isRootfalse 传给 4、5false4否false不入结果集false5是false不入结果集isRoottrue 传给孩子无孩子true → 节点 2 的 Left 置 nil3是false不入结果集isRoottrue 传给 6、7true → 节点 1 的 Right 置 nil6否true加入结果集[6]false7否true加入结果集[7]false最终结果集为[[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{}}, }, }三组用例分别验证了典型场景删除两个中间节点森林中产生 3 棵树含根、含叶子节点各自成树根被删除的退化场景root [1,2,4,2]to_delete [2]。注意该输入中出现了重复值2测试数据构造并不严格满足值互异约束由于删的是值为 2 的节点最终只剩节点1一棵树[[1]]同时验证了根节点值不在删除集合时正常保留空树边界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 -covermodeatomic -coverprofilecoverage.txt ./leetcode/...一次性对全部题解生成覆盖率报告本仓库整体覆盖率目标为 100%可以借此验证本题及其余题解的回归状态。六、边界情况与扩展思考6.1 需要注意的边界情况空树root nil时直接返回nil测试用例 3 覆盖根节点被删除原始根一旦被删除整棵树会被切分为其左右子树森林此时delNodes传入的初始isRoot true在根节点处被重置为false后再传给孩子孩子因isRoot true而各自入结果集叶子节点被删除叶子被删除时没有孩子isRoot置 true 后传给nil子树不产生任何新树仅把true返回给父节点完成剪断to_delete中出现树中不存在的值哈希表查找不会命中对该节点无影响代码天然兼容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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Go 题解 1110：删除节点并返回森林（Delete Nodes And Return Forest）的 Go 实现
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数组中的节点后原来的树会分裂成一片森林若干棵互不相交的树组成的集合。要求返回森林中每棵树的根节点结果可以按任意顺序返回。示例 1Input: 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]]。约束条件约束项范围树中节点数最多1000个节点值介于1到1000之间且各不相同to_delete.length最多1000to_delete中的值介于1到1000各不相同二、题目大意给出一棵二叉树和一个删除数组要求删除数组中相同元素值的节点输出删除后形成的森林。核心要点有三节点值全局唯一因此可以用哈希表Go 中为map[int]bool加速该节点是否应该被删除的查找删除节点本质上是剪断其父节点指向它的指针被剪断的子树会独立出来成为森林中的一棵树需要特殊判断被删除的节点是否是子树的根节点如果当前节点保留且是一棵新树的根就把它加入结果集如果当前节点被删除则其左右孩子可能成为新树的根。三、解题思路一次 DFS 边遍历边删除3.1 整体思路这是一道简单题LeetCode 难度分类为 Medium 偏易。常规做法是先遍历一遍树同时检查当前节点的值是否在to_delete中。为了把查找从 O(len(to_delete)) 降到 O(1)先把to_delete数组中的所有值放进一个map[int]bool中。遍历过程中需要同时处理两件事判断当前节点是否要加入结果集只有当当前节点保留不在删除集合中且它是某棵树的根时才把它加入结果集剪断被删除节点的父子指针如果一个节点的值在删除集合中那么它原本的父节点需要把指向它的指针置空这样它下面的子树才能脱钩成独立树。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若root nil空树直接返回nil初始化结果切片res与哈希表deleteMap遍历toDelete把每个值写入deleteMapmap[int]bool的键查找平均 O(1)调用dfsDelNodes(root, deleteMap, true, res)注意第三个参数传入true表示原始根节点天然是候选根返回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根据是否被删除更新传给孩子的 isRootisRoot 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]为例节点值在删除集合isRoot 传入值动作返回值1否true原始根加入结果集[1]isRoot 保持 false 传给孩子false保留2否false不入结果集isRootfalse 传给 4、5false4否false不入结果集false5是false不入结果集isRoottrue 传给孩子无孩子true → 节点 2 的 Left 置 nil3是false不入结果集isRoottrue 传给 6、7true → 节点 1 的 Right 置 nil6否true加入结果集[6]false7否true加入结果集[7]false最终结果集为[[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{}}, }, }三组用例分别验证了典型场景删除两个中间节点森林中产生 3 棵树含根、含叶子节点各自成树根被删除的退化场景root [1,2,4,2]to_delete [2]。注意该输入中出现了重复值2测试数据构造并不严格满足值互异约束由于删的是值为 2 的节点最终只剩节点1一棵树[[1]]同时验证了根节点值不在删除集合时正常保留空树边界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 -covermodeatomic -coverprofilecoverage.txt ./leetcode/...一次性对全部题解生成覆盖率报告本仓库整体覆盖率目标为 100%可以借此验证本题及其余题解的回归状态。六、边界情况与扩展思考6.1 需要注意的边界情况空树root nil时直接返回nil测试用例 3 覆盖根节点被删除原始根一旦被删除整棵树会被切分为其左右子树森林此时delNodes传入的初始isRoot true在根节点处被重置为false后再传给孩子孩子因isRoot true而各自入结果集叶子节点被删除叶子被删除时没有孩子isRoot置 true 后传给nil子树不产生任何新树仅把true返回给父节点完成剪断to_delete中出现树中不存在的值哈希表查找不会命中对该节点无影响代码天然兼容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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考