LeetCode-Go 题解：144. Binary Tree Preorder Traversal 二叉树前序遍历的递归与迭代实现

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根节点无左子树进入右子树访问节点2输出2节点2有左孩子3访问3输出33无子树遍历结束最终结果为[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 }该解法的模拟逻辑分三步初始化根节点入栈循环每次从栈顶弹出一个节点node先记录node.Val入栈顺序先压入node.Right再压入node.Left。由于栈是LIFO后进先出结构后压入的左孩子会先被弹出访问恰好复现了根 → 左 → 右的前序顺序。这里代码用 Go 切片模拟栈append即入栈stack[:len(stack)-1]即出栈未使用额外数据结构。复杂度对比解法时间复杂度空间复杂度额外特点解法一 递归合并切片O(n)O(h)递归栈最直观中间切片分配较多解法二 递归共享指针O(n)O(h)递归栈一次 append分配更少解法三 显式栈迭代O(n)O(h)显式栈最坏 O(n)满足 Follow up避免递归栈溢出风险其中 n 为节点数h 为树高链表状退化树的 h 趋近 n此时递归写法有栈溢出风险迭代写法更能体现工程价值。源码佐证TreeNode 定义与测试基建题目代码依赖仓库统一封装的二叉树数据结构定义在 structures/TreeNode.go// TreeNode is trees node type TreeNode struct { Val int Left *TreeNode Right *TreeNode } // NULL 方便添加测试数据 var NULL -1 63注意两点题目文件通过type TreeNode structures.TreeNode做了类型别名因此preorderTraversal系列函数直接使用统一结构体不重复定义仓库用NULL -1 63int64 最小值表示空节点占位符方便用扁平切片构造测试树。测试数据通过 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.shcd 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考