尧图网站建设 
LeetCode-Go 题解589. N 叉树的前序遍历N-ary Tree Preorder Traversal递归与非递归双解法剖析【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文基于开源仓库 LeetCode-Go 中 0589 题官方题解文档系统讲解 LeetCode 第 589 题「N 叉树的前序遍历」。文章从题目本身出发完整继承原文档中的两种解题思路与 Go 代码实现并结合仓库内的源码文件与测试用例进行纵深验证帮助你彻底掌握 N 叉树前序遍历的递归写法与基于栈的迭代写法理解逆序入栈保证前序节点始终在栈顶这一核心技巧并学会如何使用仓库自带的测试框架与数据构造函数自行验证解法。一、题目概述给定一个 N 叉树的根节点root返回其节点值的前序遍历preorder traversal。N 叉树在输入中按层序遍历进行序列化表示每组子节点之间由空值null分隔详见示例。这意味着我们可以把题目给出的扁平数组理解为遇到null表示上一组兄弟子节点结束下一组子节点开始。示例一Input: root [1,null,3,2,4,null,5,6] Output: [1,3,5,6,2,4]该示例对应的树结构为根节点1有 3 个孩子3、2、4其中节点3又有两个孩子5、6。按根 → 从左到右依次遍历子树的前序规则输出顺序为1, 3, 5, 6, 2, 4。示例二Input: root [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] Output: [1,2,3,6,7,11,14,4,8,12,5,9,13,10]该示例构建了一棵更深、更宽的 N 叉树根节点1的孩子依次为2、3、4、5节点3的孩子为6、7节点7的孩子为11节点11的孩子为14节点4的孩子为8节点8的孩子为12节点5的孩子为9节点9的孩子为13节点10的孩子为14的兄弟节点。最终前序遍历输出为[1,2,3,6,7,11,14,4,8,12,5,9,13,10]与题解预期完全一致。数据约束树中节点的数量在范围[0, 10^4]内节点值满足0 Node.val 10^4N 叉树的高度不超过1000。注意节点数可以为 0即根节点可能为nil两种解法都必须处理这一边界情况仓库测试代码中有专门的空树分支覆盖见下文测试验证一节。进阶要求Follow up题目明确指出递归解法非常直观trivial你能否用迭代的方式实现这正是本文核心要解决的问题——递归一行 DFS 即可完成而迭代解法需要借助栈数据结构并且需要精心设计入栈顺序。二、N 叉树节点定义在 LeetCode-Go 仓库中N 叉树的节点定义位于解题源码文件 589. N-ary Tree Preorder Traversal.go// Definition for a Node. type Node struct { Val int Children []*Node }与二叉树节点左右两个指针Left、Right不同N 叉树节点只有一个值Val和一个孩子节点切片Children []*Node孩子数量不固定这也正是N 叉的含义。这一结构设计决定了遍历时不能像二叉树那样硬编码先左后右而必须通过循环遍历Children切片来完成。三、核心思路递归解法递归解法是前序遍历最自然的表达先访问当前节点再依次递归遍历每个孩子节点。仓库给出的实现如下// 解法二 递归 func preorder1(root *Node) []int { res : []int{} preorderdfs(root, res) return res } func preorderdfs(root *Node, res *[]int) { if root ! nil { *res append(*res, root.Val) for i : 0; i len(root.Children); i { preorderdfs(root.Children[i], res) } } }实现要点外层函数preorder1负责初始化结果切片并通过res把切片的地址传入递归函数使所有递归层级共享同一个结果集内层函数preorderdfs先做空值判断root ! nil随后执行访问根节点 → 依次递归所有孩子的前序三步曲通过for i : 0; i len(root.Children); i循环对Children切片从左到右逐个递归恰好符合前序遍历根、左子树、右子树的推广语义——在 N 叉树中即根、第 1 个子树、第 2 个子树……。由于节点数量为n、树高不超过1000递归深度最坏为树高1000在 Go 默认栈空间下安全时间复杂度 O(n)每个节点恰好访问一次。四、核心思路非递归迭代解法递归解法一行 DFS固然简单但题目明确要求挑战迭代写法。迭代解法的关键在于二叉树非递归前序遍历需要借助栈N 叉树同样如此。仓库给出的迭代实现如下// 解法一 非递归 func preorder(root *Node) []int { res : []int{} if root nil { return res } stack : []*Node{root} for len(stack) 0 { r : stack[len(stack)-1] stack stack[:len(stack)-1] res append(res, r.Val) tmp : []*Node{} for _, v : range r.Children { tmp append([]*Node{v}, tmp...) // 逆序存点 } stack append(stack, tmp...) } return res }为什么必须逆序入栈栈是后进先出LIFO的数据结构。前序遍历要求节点的访问顺序是根 → 第 1 个孩子子树 → 第 2 个孩子子树 → ……即最早访问的孩子必须最先出栈。因此将根节点压入栈每次从栈顶弹出节点r将其值加入结果集把r的所有孩子节点逆序存入临时切片tmptmp append([]*Node{v}, tmp...)把当前孩子v不断插入切片头部实现倒序将tmp整体追加到栈中。经过逆序处理后原本位于Children切片最前面的孩子应最先访问此时恰好位于栈顶下一次循环立即被弹出访问而最后一个孩子被压到栈底最后才被访问。如此逆序入栈就保证了前序节点永远在栈顶循环直至栈空输出的结果即为 N 叉树的前序遍历。以示例一为例手动推演初始栈[1]弹出1结果[1]将孩子[3,2,4]逆序为[4,2,3]入栈栈[4,2,3]弹出3结果[1,3]将孩子[5,6]逆序为[6,5]入栈栈[4,2,6,5]弹出5结果[1,3,5]无孩子弹出6结果[1,3,5,6]无孩子弹出2结果[1,3,5,6,2]无孩子弹出4结果[1,3,5,6,2,4]无孩子栈空结束。最终输出[1,3,5,6,2,4]与题目预期完全吻合。复杂度分析时间复杂度 O(n)每个节点恰好入栈一次、出栈一次并访问一次空间复杂度 O(n)最坏情况下如根节点拥有接近n个孩子栈中同时存放大量节点此外每次弹出节点时创建的临时切片tmp也占用与孩子数量成正比的空间。五、测试用例与源码验证仓库为本题提供了完整的单元测试位于 589. N-ary Tree Preorder Traversal_test.go测试代码通过question589结构体组织输入参数 期望答案的用例对并覆盖了题目给出的两个示例qs : []question589{ { para589{[]int{1, structures.NULL, 3, 2, 4, structures.NULL, 5, 6}}, ans589{[]int{1, 3, 5, 6, 2, 4}}, }, { para589{[]int{1, structures.NULL, 2, 3, 4, 5, structures.NULL, structures.NULL, 6, 7, structures.NULL, 8, structures.NULL, 9, 10, structures.NULL, structures.NULL, 11, structures.NULL, 12, structures.NULL, 13, structures.NULL, structures.NULL, 14}}, ans589{[]int{1, 2, 3, 6, 7, 11, 14, 4, 8, 12, 5, 9, 13, 10}}, }, }空值常量与树的构造测试中使用的structures.NULL常量定义在 structures/TreeNode.go// NULL 方便添加测试数据 var NULL -1 63即用一个远小于合法节点值范围的极小整数-1 63作为空的哨兵标记用来表示层序序列化数组中的null分隔符。测试文件中的辅助函数int2NaryNode把题目给出的层序扁平数组还原为一棵真正的 N 叉树它借助队列queue逐层扫描数组每当读到非NULL的值就创建新节点并挂到当前节点的Children切片上遇到NULL则切换处理下一组孩子。这一构造逻辑正是题目每组子节点由空值null分隔的序列化规则的代码化呈现可直接作为你本地调试、复现样例数据的有力工具。边界分支覆盖测试在跑完两组用例后还显式验证了空树分支// 覆盖 root nil 分支 if got : preorder(nil); len(got) ! 0 { t.Fatalf(preorder(nil) %v, want empty, got) } if got : preorder1(nil); len(got) ! 0 { t.Fatalf(preorder1(nil) %v, want empty, got) }无论是迭代解法中if root nil { return res }的提前返回还是递归解法中if root ! nil的空值守卫都针对约束中节点数量范围为[0, 10^4]的最小边界做了防御保证空树返回空切片而非发生空指针解引用。如何运行测试在仓库根目录下执行go test -v ./leetcode/0589.N-ary-Tree-Preorder-Traversal/即可看到Test_Problem589的输出包含每个用例的输入、输出以及preorder、preorder1两个版本的调用结果测试通过即证明两种解法与题目预期一致。仓库还提供了 gotest.sh 脚本用于批量运行全部题解测试。六、从二叉树到 N 叉树举一反三N 叉树前序遍历与二叉树前序遍历的原理完全一致差异仅在孩子数量的表达上维度二叉树前序遍历N 叉树前序遍历访问顺序根 → 左子树 → 右子树根 → 第 1 个子树 → 第 2 个子树 → …节点定义Left、Right两个指针Children []*Node切片递归写法两处递归调用循环内递归调用迭代写法右孩子先入栈、左孩子后入栈孩子整体逆序入栈两者的迭代解法本质同源都是利用栈的 LIFO 特性 逆序压栈保证下一个要访问的节点永远位于栈顶。理解了本题的逆序入栈技巧二叉树的迭代前序遍历preorderTraversal先压右孩子再压左孩子也就一通百通。仓库中与之配套的序列化与测试基建同样适用于同类树题目structures包下的 TreeNode.go 提供二叉树构造工具而本题测试文件的int2NaryNode则示范了 N 叉树的构造模式两者结合可作为你扩展练习其他树形遍历题如后序、层序的模板。七、小结递归解法preorderdfs按根 → 循环递归所有孩子的顺序访问代码最简洁适合快速 AC 与理解前序语义迭代解法借助栈 孩子逆序入栈满足题目 Follow up 要求时间复杂度 O(n)、空间复杂度 O(n)是面试中更受青睐的写法工程佐证仓库在 589. N-ary Tree Preorder Traversal.go 中提供两种可运行解法在 589. N-ary Tree Preorder Traversal_test.go 中提供完整测试含空树边界并在 structures/TreeNode.go 中定义了NULL哨兵常量用于层序序列化测试数据的构造。建议读者先独立写出递归版本再基于栈重写迭代版本最后用仓库的测试用例与go test命令交叉验证即可完整掌握这道经典 N 叉树遍历题的两种解法。【免费下载链接】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 题解：589. N 叉树的前序遍历（N-ary Tree Preorder Traversal）递归与非递归双解法剖析
LeetCode-Go 题解589. N 叉树的前序遍历N-ary Tree Preorder Traversal递归与非递归双解法剖析【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文基于开源仓库 LeetCode-Go 中 0589 题官方题解文档系统讲解 LeetCode 第 589 题「N 叉树的前序遍历」。文章从题目本身出发完整继承原文档中的两种解题思路与 Go 代码实现并结合仓库内的源码文件与测试用例进行纵深验证帮助你彻底掌握 N 叉树前序遍历的递归写法与基于栈的迭代写法理解逆序入栈保证前序节点始终在栈顶这一核心技巧并学会如何使用仓库自带的测试框架与数据构造函数自行验证解法。一、题目概述给定一个 N 叉树的根节点root返回其节点值的前序遍历preorder traversal。N 叉树在输入中按层序遍历进行序列化表示每组子节点之间由空值null分隔详见示例。这意味着我们可以把题目给出的扁平数组理解为遇到null表示上一组兄弟子节点结束下一组子节点开始。示例一Input: root [1,null,3,2,4,null,5,6] Output: [1,3,5,6,2,4]该示例对应的树结构为根节点1有 3 个孩子3、2、4其中节点3又有两个孩子5、6。按根 → 从左到右依次遍历子树的前序规则输出顺序为1, 3, 5, 6, 2, 4。示例二Input: root [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] Output: [1,2,3,6,7,11,14,4,8,12,5,9,13,10]该示例构建了一棵更深、更宽的 N 叉树根节点1的孩子依次为2、3、4、5节点3的孩子为6、7节点7的孩子为11节点11的孩子为14节点4的孩子为8节点8的孩子为12节点5的孩子为9节点9的孩子为13节点10的孩子为14的兄弟节点。最终前序遍历输出为[1,2,3,6,7,11,14,4,8,12,5,9,13,10]与题解预期完全一致。数据约束树中节点的数量在范围[0, 10^4]内节点值满足0 Node.val 10^4N 叉树的高度不超过1000。注意节点数可以为 0即根节点可能为nil两种解法都必须处理这一边界情况仓库测试代码中有专门的空树分支覆盖见下文测试验证一节。进阶要求Follow up题目明确指出递归解法非常直观trivial你能否用迭代的方式实现这正是本文核心要解决的问题——递归一行 DFS 即可完成而迭代解法需要借助栈数据结构并且需要精心设计入栈顺序。二、N 叉树节点定义在 LeetCode-Go 仓库中N 叉树的节点定义位于解题源码文件 589. N-ary Tree Preorder Traversal.go// Definition for a Node. type Node struct { Val int Children []*Node }与二叉树节点左右两个指针Left、Right不同N 叉树节点只有一个值Val和一个孩子节点切片Children []*Node孩子数量不固定这也正是N 叉的含义。这一结构设计决定了遍历时不能像二叉树那样硬编码先左后右而必须通过循环遍历Children切片来完成。三、核心思路递归解法递归解法是前序遍历最自然的表达先访问当前节点再依次递归遍历每个孩子节点。仓库给出的实现如下// 解法二 递归 func preorder1(root *Node) []int { res : []int{} preorderdfs(root, res) return res } func preorderdfs(root *Node, res *[]int) { if root ! nil { *res append(*res, root.Val) for i : 0; i len(root.Children); i { preorderdfs(root.Children[i], res) } } }实现要点外层函数preorder1负责初始化结果切片并通过res把切片的地址传入递归函数使所有递归层级共享同一个结果集内层函数preorderdfs先做空值判断root ! nil随后执行访问根节点 → 依次递归所有孩子的前序三步曲通过for i : 0; i len(root.Children); i循环对Children切片从左到右逐个递归恰好符合前序遍历根、左子树、右子树的推广语义——在 N 叉树中即根、第 1 个子树、第 2 个子树……。由于节点数量为n、树高不超过1000递归深度最坏为树高1000在 Go 默认栈空间下安全时间复杂度 O(n)每个节点恰好访问一次。四、核心思路非递归迭代解法递归解法一行 DFS固然简单但题目明确要求挑战迭代写法。迭代解法的关键在于二叉树非递归前序遍历需要借助栈N 叉树同样如此。仓库给出的迭代实现如下// 解法一 非递归 func preorder(root *Node) []int { res : []int{} if root nil { return res } stack : []*Node{root} for len(stack) 0 { r : stack[len(stack)-1] stack stack[:len(stack)-1] res append(res, r.Val) tmp : []*Node{} for _, v : range r.Children { tmp append([]*Node{v}, tmp...) // 逆序存点 } stack append(stack, tmp...) } return res }为什么必须逆序入栈栈是后进先出LIFO的数据结构。前序遍历要求节点的访问顺序是根 → 第 1 个孩子子树 → 第 2 个孩子子树 → ……即最早访问的孩子必须最先出栈。因此将根节点压入栈每次从栈顶弹出节点r将其值加入结果集把r的所有孩子节点逆序存入临时切片tmptmp append([]*Node{v}, tmp...)把当前孩子v不断插入切片头部实现倒序将tmp整体追加到栈中。经过逆序处理后原本位于Children切片最前面的孩子应最先访问此时恰好位于栈顶下一次循环立即被弹出访问而最后一个孩子被压到栈底最后才被访问。如此逆序入栈就保证了前序节点永远在栈顶循环直至栈空输出的结果即为 N 叉树的前序遍历。以示例一为例手动推演初始栈[1]弹出1结果[1]将孩子[3,2,4]逆序为[4,2,3]入栈栈[4,2,3]弹出3结果[1,3]将孩子[5,6]逆序为[6,5]入栈栈[4,2,6,5]弹出5结果[1,3,5]无孩子弹出6结果[1,3,5,6]无孩子弹出2结果[1,3,5,6,2]无孩子弹出4结果[1,3,5,6,2,4]无孩子栈空结束。最终输出[1,3,5,6,2,4]与题目预期完全吻合。复杂度分析时间复杂度 O(n)每个节点恰好入栈一次、出栈一次并访问一次空间复杂度 O(n)最坏情况下如根节点拥有接近n个孩子栈中同时存放大量节点此外每次弹出节点时创建的临时切片tmp也占用与孩子数量成正比的空间。五、测试用例与源码验证仓库为本题提供了完整的单元测试位于 589. N-ary Tree Preorder Traversal_test.go测试代码通过question589结构体组织输入参数 期望答案的用例对并覆盖了题目给出的两个示例qs : []question589{ { para589{[]int{1, structures.NULL, 3, 2, 4, structures.NULL, 5, 6}}, ans589{[]int{1, 3, 5, 6, 2, 4}}, }, { para589{[]int{1, structures.NULL, 2, 3, 4, 5, structures.NULL, structures.NULL, 6, 7, structures.NULL, 8, structures.NULL, 9, 10, structures.NULL, structures.NULL, 11, structures.NULL, 12, structures.NULL, 13, structures.NULL, structures.NULL, 14}}, ans589{[]int{1, 2, 3, 6, 7, 11, 14, 4, 8, 12, 5, 9, 13, 10}}, }, }空值常量与树的构造测试中使用的structures.NULL常量定义在 structures/TreeNode.go// NULL 方便添加测试数据 var NULL -1 63即用一个远小于合法节点值范围的极小整数-1 63作为空的哨兵标记用来表示层序序列化数组中的null分隔符。测试文件中的辅助函数int2NaryNode把题目给出的层序扁平数组还原为一棵真正的 N 叉树它借助队列queue逐层扫描数组每当读到非NULL的值就创建新节点并挂到当前节点的Children切片上遇到NULL则切换处理下一组孩子。这一构造逻辑正是题目每组子节点由空值null分隔的序列化规则的代码化呈现可直接作为你本地调试、复现样例数据的有力工具。边界分支覆盖测试在跑完两组用例后还显式验证了空树分支// 覆盖 root nil 分支 if got : preorder(nil); len(got) ! 0 { t.Fatalf(preorder(nil) %v, want empty, got) } if got : preorder1(nil); len(got) ! 0 { t.Fatalf(preorder1(nil) %v, want empty, got) }无论是迭代解法中if root nil { return res }的提前返回还是递归解法中if root ! nil的空值守卫都针对约束中节点数量范围为[0, 10^4]的最小边界做了防御保证空树返回空切片而非发生空指针解引用。如何运行测试在仓库根目录下执行go test -v ./leetcode/0589.N-ary-Tree-Preorder-Traversal/即可看到Test_Problem589的输出包含每个用例的输入、输出以及preorder、preorder1两个版本的调用结果测试通过即证明两种解法与题目预期一致。仓库还提供了 gotest.sh 脚本用于批量运行全部题解测试。六、从二叉树到 N 叉树举一反三N 叉树前序遍历与二叉树前序遍历的原理完全一致差异仅在孩子数量的表达上维度二叉树前序遍历N 叉树前序遍历访问顺序根 → 左子树 → 右子树根 → 第 1 个子树 → 第 2 个子树 → …节点定义Left、Right两个指针Children []*Node切片递归写法两处递归调用循环内递归调用迭代写法右孩子先入栈、左孩子后入栈孩子整体逆序入栈两者的迭代解法本质同源都是利用栈的 LIFO 特性 逆序压栈保证下一个要访问的节点永远位于栈顶。理解了本题的逆序入栈技巧二叉树的迭代前序遍历preorderTraversal先压右孩子再压左孩子也就一通百通。仓库中与之配套的序列化与测试基建同样适用于同类树题目structures包下的 TreeNode.go 提供二叉树构造工具而本题测试文件的int2NaryNode则示范了 N 叉树的构造模式两者结合可作为你扩展练习其他树形遍历题如后序、层序的模板。七、小结递归解法preorderdfs按根 → 循环递归所有孩子的顺序访问代码最简洁适合快速 AC 与理解前序语义迭代解法借助栈 孩子逆序入栈满足题目 Follow up 要求时间复杂度 O(n)、空间复杂度 O(n)是面试中更受青睐的写法工程佐证仓库在 589. N-ary Tree Preorder Traversal.go 中提供两种可运行解法在 589. N-ary Tree Preorder Traversal_test.go 中提供完整测试含空树边界并在 structures/TreeNode.go 中定义了NULL哨兵常量用于层序序列化测试数据的构造。建议读者先独立写出递归版本再基于栈重写迭代版本最后用仓库的测试用例与go test命令交叉验证即可完整掌握这道经典 N 叉树遍历题的两种解法。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考