LC144 · 前序遍历 · 工程执行实验室
第一次到达即记录
前序遍历 = 每次第一次到达一个节点，就立刻把它加入答案。用 current、ans、 递归栈/显式栈把执行过程讲清楚，并分开理解递归版与迭代版。
3
/ \
9 20
/ \
15 7核心心智模型
前序遍历 = 每次第一次到达一个节点，就立刻把它加入答案。
- · 访问顺序口诀：自己 → 左子树 → 右子树（根-左-右）。
- · 关键不是背口诀，而是「第一次到达」就立刻 append。
- · 左子树整棵处理完，才回到当前节点继续右子树（递归返回后自然发生）。
ans 中保存的是所有已经第一次到达过的节点；stack/递归栈中保存的是还没展开但之后必须访问的节点。
进入节点时立刻 append，再 dfs(Left)、dfs(Right)。暂停状态由系统调用栈保存。
pop 当前节点并 append；先 push 右孩子、再 push 左孩子，利用栈 LIFO 模拟「先左后右」。
题目与输入：示例树与前序目标输出
给定二叉树：根 3，左孩子 9，右子树 20-15-7。前序遍历的目标输出是 [3, 9, 20, 15, 7]——根 3 最先出现，然后整棵左子树，再整棵右子树。
先看清树结构和期望序列，后面每一步都能对照「为什么是这个顺序」。
状态表 · current / ans / 栈
| current | ans | stack（显式，栈顶在右） | 下一步 | 动作 |
|---|---|---|---|---|
| current = 3（节点 1） | [] | [] | 即将学习前序规则 | 读题 |
目标输出 [3,9,20,15,7]
1func preorderTraversal(root *TreeNode) []int {2 ans := []int{}3 var dfs func(*TreeNode)4 dfs = func(node *TreeNode) {5 if node == nil {6 return7 }8 ans = append(ans, node.Val)9 dfs(node.Left)10 dfs(node.Right)11 }12 dfs(root)13 return ans14}
展开迭代版（对比 push 顺序）
func preorderTraversal(root *TreeNode) []int {
if root == nil {
return nil
}
ans := []int{}
stack := []*TreeNode{root}
for len(stack) > 0 {
n := len(stack)
node := stack[n-1]
stack = stack[:n-1]
ans = append(ans, node.Val)
if node.Right != nil {
stack = append(stack, node.Right)
}
if node.Left != nil {
stack = append(stack, node.Left)
}
}
return ans
}- 时间
- O(n)
- 空间
- O(h)
每个节点恰访问一次，共 n 个节点。
h 为树高；递归用系统调用栈，迭代用显式 stack，最坏退化链表时 O(n)。
Morris 前序遍历可做到额外空间 O(1)，但本页主讲递归/栈解法。
前序遍历按照 根-左-右 的顺序访问。递归写法是在进入节点时立刻加入答案，然后递归左子树和右子树；迭代写法用栈模拟递归，因为栈后进先出，所以要先压右孩子再压左孩子。每个节点访问一次，时间 O(n)，空间 O(h)，最坏 O(n)。
前序是「先自己」；中序是「左完才自己」；后序是「左右完才自己」。处理时机完全不同。
栈是 LIFO。要先 push 右孩子、再 push 左孩子，这样 pop 时才会先处理左子树。
递归/显式栈版本空间是 O(h)，最坏 O(n)，不是 O(1)。
空树应直接返回 nil/空切片，否则迭代版会对空指针解引用。