原始题目
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
cout << node->val << " ";
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
问：当前代码是哪种遍历？如何调整代码实现另几种遍历？
答案
当前代码是 层序遍历（Level-order，即 BFS），用 queue 实现。对这棵 3 结点树（1 的左=2、右=3）输出：
1 2 3
解析
为什么是层序遍历
核心证据是用了 queue（FIFO 队列）：从根入队，每次取出队首结点访问，再把它的左右孩子按顺序入队——保证“一层一层、从左到右”地访问。这正是层序（广度优先）的特征。
怎么调成另几种遍历
二叉树遍历共 4 种：1 种层序（队列/BFS）+ 3 种深度优先（递归/栈）。题目说“另两种”，实际是 3 种 DFS，它们只差一个 cout 的位置（相对左右递归调用的先后）：
| 遍历 | 访问时机 | 本题输出 |
|---|---|---|
| 前序 preorder | 根→左→右（先 cout 再递归） | 1 2 3 |
| 中序 inorder | 左→根→右（递归中间 cout） | 2 1 3 |
| 后序 postorder | 左→右→根（递归之后 cout） | 2 3 1 |
把队列代码换成递归即可：
// 前序：先访问，再递归左右
void preorder(TreeNode* n) {
if (!n) return;
cout << n->val << " ";
preorder(n->left);
preorder(n->right);
}
// 中序：把 cout 移到两次递归之间
// 后序：把 cout 移到两次递归之后
走一遍示例
这棵树的四种结果：
- 层序（队列）：
1 2 3 - 前序：
1 2 3（先根 1，再左子树 2，再右子树 3） - 中序：
2 1 3（左 2，根 1，右 3） - 后序：
2 3 1（左 2，右 3，根 1）
易错点总结
- 队列 = 层序（广度优先），栈/递归 = 深度优先：看清容器就能判断遍历类型。
- 三种 DFS 只差 cout 位置：前序在最前、中序在中间、后序在最后。
- “同序”是巧合：本题层序与前序都输出
1 2 3，只是因为树太浅（只有两层）。树再深一层，四种结果就会完全不同。 - 显式栈实现：前序直接栈（
push右再push左）即可；中序需先压左链、后序常用双栈或访问标记，比递归繁琐，初赛更常考递归写法。
思考题
如果把 queue 换成 stack，并先 push(node->left) 再 push(node->right)，输出会变成哪种遍历？
点击查看答案
会变成前序遍历 的“镜像”变体：栈是 LIFO，先 push 左再 push 右，则右先出，访问顺序是 根→右→左（逆前序）。标准前序（根→左→右）需要 先 push 右孩子、再 push 左孩子。
