二叉树遍历是树形结构的基础操作，前序、中序、后序、层序四种遍历方式各有用途。掌握递归与迭代两种实现，是解决所有树形问题的起点。
一、四种遍历
1
/ \
2 3
/ \
4 5
前序（根左右）: 1 2 4 5 3
中序（左根右）: 4 2 5 1 3
后序（左右根）: 4 5 2 3 1
层序（BFS）: 1 2 3 4 5
Mermaid · 渲染中（下方为源码）
graph TD 1 --> 2 1 --> 3 2 --> 4 2 --> 5
二、递归实现
void preorder(TreeNode root, List<Integer> res) {
if (root == null) return;
res.add(root.val); // 根
preorder(root.left, res); // 左
preorder(root.right, res); // 右
}
void inorder(TreeNode root, List<Integer> res) {
if (root == null) return;
inorder(root.left, res); // 左
res.add(root.val); // 根
inorder(root.right, res); // 右
}
void postorder(TreeNode root, List<Integer> res) {
if (root == null) return;
postorder(root.left, res); // 左
postorder(root.right, res); // 右
res.add(root.val); // 根
}三、迭代实现
前序（栈）
List<Integer> preorderIterative(TreeNode root) {
List<Integer> res = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
if (root != null) 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;
}中序（栈 + 指针）
List<Integer> inorderIterative(TreeNode root) {
List<Integer> res = 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();
res.add(cur.val);
cur = cur.right;
}
return res;
}后序（双栈 / 反转前序）
// 技巧：前序(根左右) → 改为(根右左) → 反转 = (左右根) = 后序
List<Integer> postorderIterative(TreeNode root) {
LinkedList<Integer> res = new LinkedList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
if (root != null) stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
res.addFirst(node.val); // 头插
if (node.left != null) stack.push(node.left);
if (node.right != null) stack.push(node.right);
}
return res;
}层序（BFS）
List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
res.add(level);
}
return res;
}四、由遍历序列重建树
| 已知 | 能否唯一确定 |
|---|---|
| 前序 + 中序 | ✅ |
| 后序 + 中序 | ✅ |
| 前序 + 后序 | ❌（不唯一，除非满二叉树） |
| 层序 + 中序 | ✅ |
// 前序 + 中序 → 建树（LeetCode 105）
TreeNode build(int[] pre, int[] in, int preL, int preR, int inL, int inR) {
if (preL > preR) return null;
TreeNode root = new TreeNode(pre[preL]);
int rootIdx = inMap.get(pre[preL]); // 中序中根的位置
int leftSize = rootIdx - inL;
root.left = build(pre, in, preL+1, preL+leftSize, inL, rootIdx-1);
root.right = build(pre, in, preL+leftSize+1, preR, rootIdx+1, inR);
return root;
}五、Morris 遍历（O(1) 空间）
利用叶子节点的空指针（线索）避免栈：
- 中序 Morris：找到左子树最右节点，临时连回当前节点
- 时间 O(n)，空间 O(1)
六、面试要点
- 递归三行：根的位置决定前/中/后序
- 迭代中序：栈 + 指针一路向左
- 层序：BFS + 按层分组
- 重建树：前/后序定根，中序分左右
- LeetCode：94/144/145（三种遍历）、102（层序）、105/106（重建树）、230（BST 第 k 小）