LeetCode 144. 二叉树的前序遍历
题目描述
题意分析
返回二叉树所有节点值的前序遍历序列。前序的顺序是先访问当前根节点，再完整访问它的左子树，最后完整访问它的右子树；每棵子树内部也遵守同样的顺序。
这里的“左、右”是整棵子树，而不只是左右两个直接孩子。每个真实节点恰好输出一次，节点值相同也不能省略；空树返回空列表。题目既可以按定义递归完成，进阶则要求用迭代实现相同的访问顺序。
解法：栈模拟前序遍历
核心思路
[!blue]
递归遍历时，函数调用栈会保存尚未处理的工作。改为迭代后，可以显式维护一个栈，栈中的每个节点都表示一棵尚未开始访问的子树；栈顶就是下一棵应该处理的子树。
前序要求根先输出，因此弹出一个节点后，立即把它的值加入结果。随后还要处理它的左、右子树。栈是后进先出，要让左子树先开始，就必须先压入右孩子，再压入左孩子。
这不只保证左孩子先于右孩子访问，也保证整棵左子树先完成。处理左子树时新压入的后续节点，始终位于原来待处理的右子树之上；只有左子树的工作全部出栈后，才轮到那棵右子树。因此，局部的压栈顺序可以保持整棵树的前序顺序。
只把非空孩子入栈。根节点先入栈，其余节点只会在父节点被处理时入栈一次，所以不会遗漏或重复访问。栈清空时，所有尚未处理的工作也就全部完成。
解题步骤
- 创建空结果列表，若根节点为空则直接返回。
- 将根节点压入栈。
- 栈非空时弹出栈顶节点，立即将它的值加入结果。
- 先压入非空的右孩子，再压入非空的左孩子。
- 重复直到栈为空，返回结果列表。
代码实现
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
res.add(node.val);
// 右孩子先入栈，左孩子才能先出栈访问。
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
return res;
}
}
func preorderTraversal(root *TreeNode) []int {
res := make([]int, 0)
if root == nil {
return res
}
stack := []*TreeNode{
root,
}
for len(stack) > 0 {
node := stack[len(stack)-1]
stack = stack[:len(stack)-1]
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
}
复杂度分析
- 时间复杂度：$O(n)$，
n为节点数。每个节点入栈、出栈并写入结果各一次。- 空间复杂度：$O(h)$，不计结果列表，
h为树高。栈保存当前路径各层尚未处理的另一侧子树，最坏为 $O(n)$；结果本身占 $O(n)$。单支链上显式栈可以始终只有一个节点，$O(h)$ 是一般上界。
关键点总结
[!green]
- 栈中的节点代表尚未开始处理的子树，弹出后先输出根节点。
- 先压右、再压左，让左子树及其后续工作始终位于右子树之上。
- 只让非空节点入栈，结束条件就是没有待处理的子树。
解法二：递归遍历
核心思路
[!blue]
前序遍历的定义本身就是递归的：访问当前根节点，然后以前序顺序遍历左子树，再以前序顺序遍历右子树。定义
preorder(node, result)将以node为根的整棵子树按前序追加到结果末尾，就可以直接把这三步写进函数。当前节点为空时，这棵子树没有内容，直接返回。否则先追加当前值，再调用左递归；左递归完成整棵左子树后才返回，随后才开始右递归，因此保证的是完整的“根、左子树、右子树”顺序。
所有递归调用共用同一个结果列表，每个非空节点只负责追加自己的值，不需要为每棵子树创建列表再合并。访问位置决定遍历顺序，这里必须在两次递归之前记录当前节点。
解题步骤
- 创建空结果列表，从根节点调用递归函数。
- 节点为空则返回；否则先追加当前节点值。
- 递归遍历整棵左子树，再递归遍历整棵右子树。
- 根节点对应的递归返回后，结果列表就是完整前序序列。
代码实现
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
preorder(root, result);
return result;
}
private void preorder(TreeNode node, List<Integer> result) {
if (node == null) {
return;
}
result.add(node.val);
preorder(node.left, result);
preorder(node.right, result);
}
}
func preorderTraversal(root *TreeNode) []int {
result := make([]int, 0)
var preorder func(*TreeNode)
preorder = func(node *TreeNode) {
if node == nil {
return
}
result = append(result, node.Val)
preorder(node.Left)
preorder(node.Right)
}
preorder(root)
return result
}
复杂度分析
- 时间复杂度：$O(n)$，每个真实节点访问并追加一次。
- 空间复杂度：$O(h)$，不计结果列表，递归栈深度受树高限制。左右子树先后递归，不会同时保留两棵子树的完整调用栈；链状树最坏为 $O(n)$。
关键点总结
[!green]
- 递归函数负责完整遍历一棵子树，先记录根，再顺序递归左右子树。
- 结果列表在本次遍历内共享，函数返回只表示当前子树处理完毕。
- 递归依赖调用栈保存工作，前面的迭代解法则显式保存待处理子树。
易错点总结
[!yellow]
- 先压左再压右，会使右子树先被弹出，得到错误的访问顺序。
- 同时在孩子入栈时记录它们的值，会提前输出右孩子，破坏“先完成整棵左子树”的要求。此实现统一在出栈时记录。
- 空根节点不能直接压入 Java 的
ArrayDeque，应提前返回空结果；孩子入栈前也要判空。- 把栈改成队列会按层处理节点，不能保持前序的深度优先顺序。
- 递归实现必须在两次递归之前记录当前节点；改变记录位置，就会变成中序或后序遍历。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 94. 二叉树的中序遍历 | 简单 | 栈模拟过程相同，但本题先输出根，原题要先完成左子树再输出根。 |
| 145. 二叉树的后序遍历 | 简单 | 本题根先输出，后序要求左右子树都处理完再输出根，栈中状态安排不同。 |