二叉树的遍历：前序、中序、后序、层序
遍历二叉树，说白了就是按照某种规则，把树里的每个节点都访问一遍，而且不重复、不遗漏。这就像你走进一个迷宫，每个房间都要走到，但走法不同——有人喜欢先看当前房间，再进左边和右边；有人非要先把左边所有房间看完，才肯看中间。
我个人习惯把遍历理解为“打印顺序”。你想想看，一棵二叉树存了一堆数字，你用什么顺序把它们打印出来？这就是遍历的核心。
四种遍历方式速览
先给个全景图。二叉树遍历分两大类：深度优先（DFS）和广度优先（BFS）。深度优先里又分三种：前序、中序、后序。广度优先就是层序遍历。
核心记忆法：“根”的位置决定名字。根在前就是前序，根在中间就是中序，根在后就是后序。
前序遍历（根左右）
前序遍历的顺序是：根节点 → 左子树 → 右子树。说白了就是“先看自己，再看左边，最后看右边”。
我在项目中遇到过这样一个场景：用前序遍历来序列化二叉树，把树结构存到文件里。因为前序遍历的第一个节点一定是根，反序列化时很好定位。
// 递归实现前序遍历
void preorder(TreeNode* root) {
if (root == NULL) return;
printf("%d ", root->val); // 先访问根
preorder(root->left); // 再遍历左子树
preorder(root->right); // 最后遍历右子树
}小技巧：递归代码看着简单，但面试官经常让你写非递归版本。非递归前序遍历用栈模拟，先把根入栈，然后循环：弹出节点→访问→右孩子入栈→左孩子入栈（注意顺序，先右后左，因为栈是后进先出）。
中序遍历（左根右）
中序遍历的顺序是：左子树 → 根节点 → 右子树。这个顺序有个特别重要的性质——对于二叉搜索树（BST），中序遍历的结果是递增有序的。
我记得有一次做数据库索引优化，需要验证一棵B+树的变体是否正确构建。我直接写了个中序遍历，打印出来一看，果然有序，心里就踏实了。
// 递归实现中序遍历
void inorder(TreeNode* root) {
if (root == NULL) return;
inorder(root->left); // 先遍历左子树
printf("%d ", root->val); // 再访问根
inorder(root->right); // 最后遍历右子树
}避坑指南：我曾经在非递归中序遍历上栽过跟头。核心逻辑是：一直往左走，把沿途节点压栈，直到NULL；然后弹出栈顶访问，再转向右子树。很多人忘了“转向右子树”这一步，导致死循环。记住：左到底→弹出访问→往右一步。
后序遍历（左右根）
后序遍历的顺序是：左子树 → 右子树 → 根节点。这个顺序在什么场景下有用？删除二叉树的时候。你想想看，要删除一棵树，得先把孩子删了，才能删父亲吧？后序遍历正好满足这个需求。
// 递归实现后序遍历
void postorder(TreeNode* root) {
if (root == NULL) return;
postorder(root->left); // 先遍历左子树
postorder(root->right); // 再遍历右子树
printf("%d ", root->val); // 最后访问根
}后序遍历的非递归实现是三种里最麻烦的。需要两个栈，或者用一个栈加一个标记变量记录上次访问的节点。嗯，这里要注意：只有当一个节点的左右子树都访问完了，才能访问它自己。
层序遍历（广度优先）
层序遍历就是一层一层地扫过去，从上到下，从左到右。这个用递归不太好写，队列才是它的最佳搭档。
// 层序遍历（使用队列）
void levelorder(TreeNode* root) {
if (root == NULL) return;
Queue* q = createQueue();
enqueue(q, root);
while (!isEmpty(q)) {
TreeNode* cur = dequeue(q);
printf("%d ", cur->val);
if (cur->left) enqueue(q, cur->left);
if (cur->right) enqueue(q, cur->right);
}
}层序遍历的变种题：面试常考“之字形遍历”（也叫锯齿形遍历）。其实就是层序遍历加一个标志位，奇数层从左到右，偶数层从右到左。实现时可以用双端队列，或者普通队列加一个反转操作。
四种遍历的复杂度对比
| 遍历方式 | 时间复杂度 | 空间复杂度（递归） | 空间复杂度（迭代） | 核心数据结构 |
|---|---|---|---|---|
| 前序遍历 | O(n) | O(h) | O(h) | 栈 |
| 中序遍历 | O(n) | O(h) | O(h) | 栈 |
| 后序遍历 | O(n) | O(h) | O(h) | 栈（双栈或标记） |
| 层序遍历 | O(n) | O(h) | O(w) | 队列 |
注：n 是节点数，h 是树高，w 是树的最大宽度。最坏情况下 h = n（链状树），最好情况下 h = log n（平衡树）。
一个例子看懂全部
假设我们有这样一棵二叉树：
1
/ \
2 3
/ \ \
4 5 6四种遍历的结果分别是：
- 前序遍历：1 2 4 5 3 6
- 中序遍历：4 2 5 1 3 6
- 后序遍历：4 5 2 6 3 1
- 层序遍历：1 2 3 4 5 6
你仔细看看中序遍历的结果，是不是左边都比1小，右边都比1大？这就是BST的验证原理。
我的个人习惯：刷题时如果遇到“根据两种遍历结果重建二叉树”的题，我一般先看中序遍历。因为中序遍历能告诉你左右子树的边界。前序+中序可以重建，后序+中序也可以重建，但前序+后序不行——除非是满二叉树。
递归 vs 迭代：怎么选？
递归代码简洁，但函数调用有开销，而且深度太大会栈溢出。迭代代码稍复杂，但可控性好。
我建议：日常写算法题用递归，生产环境或处理大数据量时用迭代。曾经我在嵌入式设备上写树遍历，递归深度超过500就崩了，改成迭代后稳稳的。
嗯，四种遍历就讲到这里。你想想看，其实核心就两样东西：递归顺序和栈/队列的模拟。把这两个搞明白，二叉树遍历这块就通了。
公众号:蓝海资料掘金营，微信deep3321