企业官网建设流程全解析

LeetCode-Go 题解：144. Binary 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 第 144 题「Binary Tree Preorder Traversal（二叉树的前序遍历）」展开，完整讲解该题在 LeetCode-Go 仓库中的三类 Go 实现：两种递归写法与一种基于显式栈的迭代写法。读完本文，你将掌握前序遍历的访问顺序原理、递归与迭代之间的转换技巧，并能结合仓库中的TreeNode结构、测试用例与序列化辅助函数，在本地验证这些解法。

题目：问题描述与示例

原题完整描述见 0144.Binary-Tree-Preorder-Traversal.md。

给定一棵二叉树，返回其节点值的前序遍历结果（preorder traversal）。

示例：

Input: [1,null,2,3] 1 \ 2 / 3 Output: [1,2,3]

该输入采用 LeetCode 的层序序列化格式：[1,null,2,3]表示根节点为1，根节点没有左孩子（null），右孩子为2，而2的左孩子为3。前序遍历的访问顺序是根 → 左子树 → 右子树，因此输出为[1, 2, 3]。

Follow up（进阶要求）：题目明确指出，递归解法是平凡的（trivial），能否用迭代方式实现？

这个 Follow up 是本题真正的考察点，对应仓库中解法三（显式栈模拟）的实现。

解题思路总览：前序遍历的访问顺序

前序遍历的核心规则只有一条：每访问到一个节点，先记录该节点本身的值，再递归地访问其左子树，最后访问其右子树。对于上面的示例树：

1. 访问根节点1，输出1；
2. 根节点无左子树；
3. 进入右子树，访问节点2，输出2；
4. 节点2有左孩子3，访问3，输出3；
5. 3无子树，遍历结束，最终结果为[1, 2, 3]。

由于递归天然符合"函数调用栈"的语义，递归写法最直观；而迭代写法需要手动维护一个栈，在入栈顺序上做文章（先压右孩子、再压左孩子，弹出时即先左后右），从而复刻递归的访问次序。

解法一：递归 + 合并切片

第一种递归实现位于 144. Binary Tree Preorder Traversal.go：

// 解法一 递归 func preorderTraversal(root *TreeNode) []int { res := []int{} if root != nil { res = append(res, root.Val) tmp := preorderTraversal(root.Left) for _, t := range tmp { res = append(res, t) } tmp = preorderTraversal(root.Right) for _, t := range tmp { res = append(res, t) } } return res }

该写法逐层返回"以当前节点为根的子树的前序序列"：

• 递归基：root == nil时返回空切片；
• 先把自己加入res，再依次拼接左子树、右子树返回的切片。

由于每次递归调用都会创建新的res切片并通过append合并左右子树结果，代码结构最贴合"分而治之"的直觉，易于理解，但会产生较多的中间切片分配。append在底层容量不足时会自动扩容并拷贝，多个节点层级叠加后，总拷贝量约为 O(n·h)（h 为树高），实际 LeetCode 用例规模下性能仍然完全可用。

解法二：递归 + 指针共享结果切片

第二种递归实现 144. Binary Tree Preorder Traversal.go 通过指针在所有递归层级间共享同一个结果切片：

// 解法二 递归 func preorderTraversal1(root *TreeNode) []int { var result []int preorder(root, &result) return result } func preorder(root *TreeNode, output *[]int) { if root != nil { *output = append(*output, root.Val) preorder(root.Left, output) preorder(root.Right, output) } }

与解法一的关键差异：

• 外层preorderTraversal1只负责初始化result并调用辅助函数；
• 内层preorder通过*output = append(*output, root.Val)直接修改共享切片；
• 整个遍历过程只做一次全局的append序列，不产生中间切片的合并拷贝，内存分配次数显著少于解法一。

该写法也是很多"带引用参数的递归回溯"类题目的通用范式（例如路径收集、组合枚举），值得作为模板掌握。

解法三：迭代法，用栈模拟递归过程

针对题目的 Follow up，仓库给出了显式栈的迭代实现 144. Binary Tree Preorder Traversal.go：

// 解法三 非递归，用栈模拟递归过程 func preorderTraversal2(root *TreeNode) []int { if root == nil { return []int{} } stack, res := []*TreeNode{}, []int{} stack = append(stack, root) for len(stack) != 0 { node := stack[len(stack)-1] stack = stack[:len(stack)-1] if node != nil { res = append(res, node.Val) } if node.Right != nil { stack = append(stack, node.Right) } if node.Left != nil { stack = append(stack, node.Left) } } return res }

该解法的模拟逻辑分三步：

1. 初始化：根节点入栈；
2. 循环：每次从栈顶弹出一个节点node，先记录node.Val；
3. 入栈顺序：先压入node.Right，再压入node.Left。

由于栈是LIFO（后进先出）结构，后压入的左孩子会先被弹出访问，恰好复现了"根 → 左 → 右"的前序顺序。这里代码用 Go 切片模拟栈：append即入栈，stack[:len(stack)-1]即出栈，未使用额外数据结构。

复杂度对比：

其中 n 为节点数，h 为树高；链表状退化树的 h 趋近 n，此时递归写法有栈溢出风险，迭代写法更能体现工程价值。

源码佐证：TreeNode 定义与测试基建

题目代码依赖仓库统一封装的二叉树数据结构，定义在 structures/TreeNode.go：

// TreeNode is tree's node type TreeNode struct { Val int Left *TreeNode Right *TreeNode } // NULL 方便添加测试数据 var NULL = -1 << 63

注意两点：

1. 题目文件通过type TreeNode = structures.TreeNode做了类型别名，因此preorderTraversal系列函数直接使用统一结构体，不重复定义；
2. 仓库用NULL = -1 << 63（int64 最小值）表示"空节点"占位符，方便用扁平切片构造测试树。

测试数据通过 Ints2TreeNode 将[]int按层序还原为二叉树：取切片首元素建根，借助队列逐层为节点挂载左右孩子，遇到NULL跳过。这正是测试用例里[]int{1, structures.NULL, 2, 3}能被还原成题目示例树的原因。

测试用例与验证

题目测试位于 144. Binary Tree Preorder Traversal_test.go，覆盖了三组用例：

qs := []question144{ {para144{[]int{}}, ans144{[]int{}}}, // 空树 {para144{[]int{1}}, ans144{[]int{1}}}, // 单节点 {para144{[]int{1, structures.NULL, 2, 3}}, ans144{[]int{1, 2, 3}}}, // 题目示例 }

测试逻辑为：对每组输入调用structures.Ints2TreeNode还原出树，然后依次运行preorderTraversal、preorderTraversal1、preorderTraversal2三种解法。三种解法的输出都应与ans144.one一致。执行方式参考仓库根目录的 gotest.sh：

cd leetcode/0144.Binary-Tree-Preorder-Traversal && go test -v

也可在仓库根目录按 gotest.sh 的批量脚本方式运行全部题解测试。

延伸：前序遍历在仓库中的工程应用

前序遍历并不仅是面试题，在序列化与树的复制/打印等场景中都有直接应用。仓库 structures/TreeNode.go 提供了Tree2Preorder，用递归前序把二叉树还原成切片，与本题解法二的结构如出一辙：

// Tree2Preorder 把 二叉树 转换成 preorder 的切片 func Tree2Preorder(root *TreeNode) []int { if root == nil { return nil } if root.Left == nil && root.Right == nil { return []int{root.Val} } res := []int{root.Val} res = append(res, Tree2Preorder(root.Left)...) res = append(res, Tree2Preorder(root.Right)...) return res }

与之配套，TreeNode.go 的PreIn2Tree支持用"前序 + 中序"两个切片重建二叉树，这是前序序列与中序序列结合使用的经典场景，可作为本题学习后的进阶练习。此外，仓库中 0145.Binary-Tree-Postorder-Traversal 与 0094.Binary-Tree-Inorder-Traversal 与本题同属"三种遍历"姊妹题，迭代栈的写法可以互相印证：只要调整访问时机与入栈顺序，同一套栈模板即可覆盖前序、中序、后序三种遍历。

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