LeetCode 94. 二叉树的中序遍历
题目描述
题意分析
给定一棵二叉树，按中序遍历的次序返回全部节点值：先遍历左子树，再记录根节点，最后遍历右子树。左右子树内部也遵循同样的顺序，不能只交换根与两个直接孩子的位置。
这里是普通二叉树，不保证是二叉搜索树，所以中序结果不一定有序，也不需要排序或去重。每个节点记录一次，空树返回空列表。题目的进阶要求用迭代实现；下面先讲显式栈，再补充与之对应的递归写法。
解法：栈模拟递归中序遍历
核心思路
[!blue]
递归中序遍历会在进入左子树前记住当前节点，等左子树处理完，再回来记录当前值并进入右子树。显式栈保存的就是这些“还没记录、之后需要回来处理”的节点，相当于把递归调用中的返回位置保存下来。
cur是接下来要进入的子树入口，栈中保存等待记录的祖先节点。只要cur非空，就先把它入栈，再转向左孩子；这一步只保存节点，不记录答案，因为它的左子树必须先输出。当
cur为空时，当前左侧路径已经走完，栈顶节点的左子树也已处理完毕，因此弹出它并记录。随后令cur指向它的右孩子，按同样方式遍历右子树。右子树处理完后，再回到栈中更上层的祖先，从而始终保持“左、根、右”的顺序。循环必须在
cur非空或栈非空时继续：前者说明还有子树需要进入，后者说明还有返回后需要记录的节点。只有二者都为空，整棵树才遍历结束。
解题步骤
- 初始化空结果列表、空栈和
cur = root。- 只要
cur非空或栈非空，就继续遍历；沿cur的左孩子不断入栈，直到遇到空节点。- 弹出栈顶节点，将其值加入结果。此时它的左子树已处理完，记录时机恰好在左右子树之间。
- 将
cur指向弹出节点的右孩子，重复沿左链入栈的过程。cur和栈同时为空时返回结果。根节点为空时，循环不会执行。
代码实现
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
// 沿左链保存待访问节点，入栈时还不输出。
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
// 左子树已处理完，弹出的节点现在才能输出。
cur = stack.pop();
ans.add(cur.val);
// 再按相同流程处理右子树。
cur = cur.right;
}
return ans;
}
}
func inorderTraversal(root *TreeNode) []int {
ans := []int{}
stack := []*TreeNode{}
cur := root
for cur != nil || len(stack) > 0 {
// 沿左链保存待访问节点，入栈时还不输出。
for cur != nil {
stack = append(stack, cur)
cur = cur.Left
}
// 左子树已处理完，弹出的节点现在才能输出。
cur = stack[len(stack)-1]
stack = stack[:len(stack)-1]
ans = append(ans, cur.Val)
// 再按相同流程处理右子树。
cur = cur.Right
}
return ans
}
复杂度分析
- 时间复杂度：$O(n)$，每个节点入栈、出栈各一次，记录一次。虽然有两层循环，总操作次数仍与节点数成正比。
- 空间复杂度：$O(h)$，栈保存一条祖先路径，
h为树高；平衡树为 $O(\log n)$，最坏的链状树为 $O(n)$。这里不计返回结果本身占用的 $O(n)$ 空间。
关键点总结
[!green]
- 栈保存尚未记录的节点；沿左链入栈是在安排访问顺序，不是在输出结果。
- 弹栈时左子树已完成，记录当前值后才能进入右子树。
- 当前子树和待返回节点都处理完，遍历才结束。
补充解法：递归中序遍历
核心思路
[!blue]
定义
inorder(node)的任务为：按中序顺序，将以node为根的整棵子树追加到结果中。node为空时没有节点可记录，直接返回。对非空节点，先让左子树完成自己的遍历，再记录当前节点，最后遍历右子树。递归调用保证左右子树各自的内部顺序，三部分按“左、根、右”衔接，就得到当前整棵子树的中序结果。
调用栈会记住当前节点，以及左子树处理完后还要执行的记录、遍历右子树两步。前面的迭代写法正是把这些待返回的位置改为显式保存。结果列表在一次调用中创建，并在各层递归间共享，避免为每棵子树创建列表后再拼接。
解题步骤
- 创建空结果列表，从根节点调用递归函数。
- 当前节点为空时返回；否则先递归遍历左子树。
- 将当前节点值追加到同一个结果列表。
- 递归遍历右子树。根节点对应的递归完成后，返回结果。
代码实现
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
inorder(root, ans);
return ans;
}
private void inorder(TreeNode node, List<Integer> ans) {
if (node == null) {
return;
}
inorder(node.left, ans);
ans.add(node.val);
inorder(node.right, ans);
}
}
func inorderTraversal(root *TreeNode) []int {
ans := make([]int, 0)
var inorder func(*TreeNode)
inorder = func(node *TreeNode) {
if node == nil {
return
}
inorder(node.Left)
ans = append(ans, node.Val)
inorder(node.Right)
}
inorder(root)
return ans
}
复杂度分析
- 时间复杂度：$O(n)$，每个节点被访问并记录一次。
- 空间复杂度：$O(h)$，递归调用栈的最大深度为树高；平衡树为 $O(\log n)$，最坏的链状树为 $O(n)$。返回结果本身的 $O(n)$ 空间另计。
关键点总结
[!green]
- 每次递归负责一整棵子树，空节点就是结束条件。
- 记录当前值的位置必须在两次子树递归之间。
- 递归栈与显式栈保存的是同类信息，两种写法的辅助空间都与树高有关。
易错点总结
[!yellow]
- 只以
cur != null作为循环条件，走到空左孩子时就会提前结束，漏掉栈中尚未记录的节点。- 入栈时就记录节点值，会把根放到左子树之前，变成前序访问顺序。
- 弹栈后忘记进入该节点的右子树，会遗漏节点；继续沿原来的左指针走则可能重复访问。
- Go 弹栈时只读取栈顶却不缩短切片，节点会反复留在栈中。
- 递归调用也需要保存返回位置，其空间是树高级别，不能因为没有手写栈就写成 $O(1)$。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 144. 二叉树的前序遍历 | 简单 | 同样用栈模拟递归，区别在节点值输出相对左右子树的时机。 |
| 145. 二叉树的后序遍历 | 简单 | 同样遍历全部节点，后序需在两个孩子处理完后输出，本题在左子树后、右子树前输出。 |
| 补充题 194. 带层数的二叉树中序遍历 | 简单 | 都按左子树、根、右子树的顺序遍历；补充题还记录每个节点的层数。 |