LeetCode-Go 题解：589. N 叉树的前序遍历（N-ary Tree Preorder Traversal）递归与非递归双解法剖析

导读

本文基于开源仓库 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^4；
• N 叉树的高度不超过 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 个孩子子树 → ……"，即最早访问的孩子必须最先出栈。因此：

1. 将根节点压入栈；
2. 每次从栈顶弹出节点 r，将其值加入结果集；
3. 把 r 的所有孩子节点逆序存入临时切片 tmp（tmp = append([]*Node{v}, tmp...) 把当前孩子 v 不断插入切片头部，实现倒序）；
4. 将 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 叉树遍历题的两种解法。