企业官网建设流程全解析

• 文档
• 教程
• 知识库

导读

本文基于 algorithm-base 仓库《animation-simulation/二叉树》系列，讲解二叉树前序遍历的非递归（迭代）实现。前序遍历的顺序是"根 → 左 → 右"，在刷题与面试中，掌握其迭代写法与递归写法同等重要。读完本文，你将理解"为什么前序遍历要借助栈、为什么要先压右孩子再压左孩子"，并能独立写出 Java / Swift / Go 三种语言的通过版代码。

前序遍历是什么

前序遍历的顺序是：对于树中的某个节点，先遍历该节点本身，然后再遍历其左子树，最后遍历其右子树。

以根节点出发，前序遍历的结果序列正是"根 → 左子树全部 → 右子树全部"。这一顺序也是三种深度优先遍历（前序、中序、后序）中最直观的一种，它是后续学习中序遍历（迭代）、后序遍历（迭代）.md)以及MORRIS 前序遍历.md)的基础。对二叉树的基础概念（根节点、子树、左右子树次序）不熟悉的读者，可先阅读二叉树基础。

迭代法：用栈替代系统递归栈

为什么是栈而不是队列

回忆二叉树的层序遍历：我们借助队列（先进先出，FIFO）完成逐层访问，因为层序遍历要求"先处理先进入的节点"。

而前序遍历要求"根 → 左 → 右"的深度优先顺序：访问完当前节点后，下一步应该立刻进入它的左子树，而不是先访问"同层"的兄弟节点。这正好对应栈（先进后出，LIFO）的特性，所以前序遍历的迭代实现选择栈作为辅助数据结构。关于栈的模型、push / pop 操作与典型应用，可参考仓库中的关于栈和队列的那些事一文。

入栈顺序：先右后左

这是整个迭代法最核心、也最容易写反的一步：

栈的特性是先进后出，借助栈完成前序遍历时，应当先将右子节点入栈，再将左子节点入栈。

这样出栈时，左子节点会先被弹出处理，右子节点随后再被处理，从而满足前序遍历"先左后右"的要求。

以二叉树[1, 2, 3]为例（1 为根，左孩子 2，右孩子 3），手动模拟一遍：

1. root（节点 1）入栈，栈内：[1]；
2. 栈非空，弹出 1，记录1；其右孩子 3 入栈，左孩子 2 入栈，栈内：[3, 2]；
3. 弹出 2，记录2；2 无孩子；
4. 弹出 3，记录3；3 无孩子；
5. 栈空，结束。输出序列1 → 2 → 3，正确。

完整流程总结

用一句话概括整个算法：

当栈不为空时，栈顶元素出栈并记录；若其右孩子不为空则右孩子入栈；若其左孩子不为空则左孩子入栈。

注意：与层序遍历需要先把根节点放入队列一样，迭代前序遍历也需要先将 root 节点入栈，再进入 while 循环。

复杂度分析

• 时间复杂度：O(n)，需要对树中所有节点各访问一次；
• 空间复杂度：O(n)，栈的开销。平均情况下为 O(log n)（平衡二叉树栈深约为树高），最坏情况为 O(n)，即斜二叉树（所有节点只有左孩子或只有右孩子）时，栈中需要同时保存接近全部节点。

参考代码

Java

class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); if (root == null) return list; stack.push(root); while (!stack.isEmpty()) { TreeNode temp = stack.pop(); if (temp.right != null) { stack.push(temp.right); } if (temp.left != null) { stack.push(temp.left); } //这里也可以放到前面 list.add(temp.val); } return list; } }

Swift

class Solution { func preorderTraversal(_ root: TreeNode?) -> [Int] { var list:[Int] = [] var stack:[TreeNode] = [] guard root != nil else { return list } stack.append(root!) while !stack.isEmpty { let temp = stack.popLast() if let right = temp?.right { stack.append(right) } if let left = temp?.left { stack.append(left) } //这里也可以放到前面 list.append((temp?.val)!) } return list } }

Go

func preorderTraversal(root *TreeNode) []int { res := []int{} if root == nil { return res } stk := []*TreeNode{root} for len(stk) != 0 { temp := stk[len(stk) - 1] stk = stk[: len(stk) - 1] if temp.Right != nil { stk = append(stk, temp.Right) } if temp.Left != nil { stk = append(stk, temp.Left) } res = append(res, temp.Val) } return res }

三个版本的结构完全一致：先判空，根入栈，循环内"先取栈顶、后压右左"。其中list.add(temp.val)这一步放在出栈后立刻执行即可，因为此时temp就是要访问的节点。

与系列其他遍历实现的衔接

掌握了"栈 + 先右后左"这一思想后，可以自然衔接本仓库二叉树系列的其他文章：

• 二叉树中序遍历（迭代）：同样借助栈，但改用"指针不断向左孩子移动并入栈，指针为空时出栈并把指针指向右孩子"的策略，与前序遍历的入栈方式形成鲜明对比；
• 二叉树的后续遍历（迭代）.md)：需要额外的preNode指针记录上一个访问的节点，以判断右子树是否已被访问，是三者中实现最复杂的；
• 二叉树的前序遍历（Morris）.md)：利用树中大量空闲指针（叶子节点的 right）将空间复杂度优化到 O(1)，可作为迭代法之后进一步学习的进阶话题。

小结

迭代前序遍历的核心可归纳为三点：

1. 用栈（LIFO）而非队列，匹配深度优先的"根 → 左 → 右"顺序；
2. 先压右孩子、再压左孩子，保证出栈次序为"先左后右"；
3. 根节点先入栈，再进入 while 循环，循环内"弹出即记录、有孩子则入栈"。

掌握这份代码后，你可以在 LeetCode 144（二叉树的前序遍历）等题目上直接套用，并以此为模板扩展到中序、后序的迭代写法。

• 文档
• 教程
• 知识库