企业官网建设流程全解析

二叉树遍历这个知识点，几乎是每个学数据结构的人都要迈过去的一道坎。面试要问、考试要考、平时写点树相关的代码也绕不开。很多人在递归实现里还能勉强写出来，一到非递归就懵了，尤其是后序遍历，简直能用“玄学”来形容。这篇文章我打算用 C++ 把二叉树的三种遍历方式从头到尾拆一遍：先讲清楚递归版本里那几行代码为什么顺序换一下就变了，再用栈把递归“翻译”成非递归版本，最后补一个层序遍历作为延伸。无论你是刚学到树结构的新手，还是准备招聘面试想快速捡起来，这篇文章都适合你直接照着敲一遍。我会固定用一棵测试树贯穿全文，每个函数的输出都拿它验证，这样你跟着跑一遍就能确认自己写对了没有。

1. 先把树的骨架搭起来：节点定义与建树

学遍历之前，得先把树在内存里长什么样搞清楚。C++ 里最经典的二叉树节点定义是这种指针结构：

struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };

这个结构很好理解：val 存数据，left 和 right 分别指向左孩子和右孩子，没有孩子就是 nullptr。对比数组存储，用指针串起来的二叉树天然更适合递归处理，因为每个节点都可以当作一棵子树的根，而子树又有自己的 left 和 right，于是“递归”这个动作在结构上就自然成立了。

1.1 为什么“访问时机”决定了遍历顺序

不要直接背“根左右”“左根右”“左右根”，背了也容易混。先看清楚一个事实：三种遍历的共同点是“先左后右”，区别只有根节点在什么时候被访问。

• 先序遍历：先输出当前节点，再去处理左子树和右子树，核心是“进树就输出”。
• 中序遍历：先把左子树整个处理完，再输出当前节点，最后处理右子树，核心是“左子树回来再输出”。
• 后序遍历：左右子树都处理完，最后才输出当前节点，核心是“全部干完再汇报”。

这么一拆你会发现，所谓先序、中序、后序，命名依据就是根节点被访问在三个位置中的哪一个。后面所有递归代码，不过是把“输出”这一行放到左递归和右递归的不同位置罢了。这也解释了为什么很多教材会强调“二叉树本身是递归定义的”：每个节点的左子树和右子树仍然是一棵二叉树，所以遍历的操作可以一直套用到子树上，直到遇到空节点为止。

1.2 固定一棵测试树，后面所有输出都对它

为了让你能自己验证，我把全文统一的测试树定为下面这棵：

1 / \ 2 3 / \ \ 4 5 6

左子树挂在 1 的左边，右子树挂在 1 的右边，其中 3 没有左孩子、右孩子是 6。建树代码可以直接照抄：

TreeNode* buildExampleTree() { TreeNode* n1 = new TreeNode(1); TreeNode* n2 = new TreeNode(2); TreeNode* n3 = new TreeNode(3); TreeNode* n4 = new TreeNode(4); TreeNode* n5 = new TreeNode(5); TreeNode* n6 = new TreeNode(6); n1->left = n2; n1->right = n3; n2->left = n4; n2->right = n5; n3->right = n6; return n1; }

这棵树的遍历结果如果你能提前背下来，后面调试自己的代码就非常省事：先序 1 2 4 5 3 6，中序 4 2 5 1 3 6，后序 4 5 2 6 3 1，层序 1 2 3 4 5 6。我建议你把这四个结果抄在便利贴上，写完一个函数就对一次。别小看这一步，我见过太多人写完后序遍历对着屏幕发愣，就是因为没有标准答案可以对照。

2. 递归实现：三份代码看懂三种遍历

递归版本是理解遍历的基础，代码短得惊人，很多人背的就是这一版。这里的核心是每个函数都只做三件事：判空、递归左、递归右，再加上“输出当前节点”这个动作。输出放在哪里，就决定了遍历顺序。

2.1 先序遍历：进树就输出

void preorder(TreeNode* root) { if (!root) return; cout << root->val << " "; preorder(root->left); preorder(root->right); }

代码逻辑就是“先输出自己，再往左走，左子树走完回来再往右走”。用固定测试树走一遍：进入 1，输出 1，进入 2，输出 2，进入 4，输出 4，4 的孩子都是空，回到 2 再进入 5，输出 5……整个过程就像“走到哪报到到哪”，最后输出 1 2 4 5 3 6。先序的一个经典用途是复制一棵二叉树：你只需要先创建当前节点，然后递归创建左子树和右子树，顺序完全是先序。

2.2 中序遍历：左子树处理完再输出

void inorder(TreeNode* root) { if (!root) return; inorder(root->left); cout << root->val << " "; inorder(root->right); }

和先序只差一行位置：输出被放到了左递归和右递归之间。对测试树，结果是 4 2 5 1 3 6。注意看，它正好把 1 放到了中间，2 放到了它的左子树 4 和 5 的中间，这就是中序的“左根右”。

中序还有个很重要的性质：如果这棵树是二叉搜索树，中序遍历输出的一定是升序序列。很多算法题让“判断二叉树是不是二叉搜索树”“找第 k 小节点”，本质都是在利用中序的这个单调性。说实话，这个性质在笔试里出现频率极高，值得单独记下来。

2.3 后序遍历：左右都处理完才输出

void postorder(TreeNode* root) { if (!root) return; postorder(root->left); postorder(root->right); cout << root->val << " "; }

输出测试树的后序：4 5 2 6 3 1。根节点 1 是最后一个输出的，因为要先等它的左右子树全部处理完。

后序的一个典型用途是删除整棵树。你想删掉一个节点，必须先把它的两个孩子删掉，否则删掉父节点后你再也找不到子节点，就会内存泄漏。这个“先处理孩子再处理自己”的顺序，正好就是后序遍历。另一个相关场景是求树的高度：先知道左右子树的高度，取最大值再加一，就是当前节点的高度，这也是典型的后序思路。你观察一下代码就会发现，后序里“输出自己”的位置在两次递归之后，这种“收集完孩子信息再处理自己”的模式，在很多树形 DP 题目里都是通用套路。

2.4 递归调用栈：你的“隐式助手”

很多人卡在递归上，是因为试图人肉展开递归。三层以内的树还能展开，四层五层就很难了。正确做法是“相信你的函数定义”：如果preorder(root)的定义就是“输出 root 然后遍历左右子树”，那么当它调用preorder(root->left)时，你只需要相信这句话，不需要展开它。

递归底层靠的是一块叫“调用栈”的内存区域。每次调用函数，系统会把当前函数的状态压栈；函数返回后，再从栈里恢复状态继续执行。二叉树递归遍历里，调用栈帮你记住的就是那些“左子树还没处理完的祖先节点”。三种遍历的区别，只是“输出自己”发生在压栈前、左子树返回后还是右子树返回后。打个比方：先序像一进办事大厅就喊号，中序像把左手边窗口全办完再喊号，后序像把所有窗口都办完才喊号。系统栈就是那个帮你排队叫号的工作人员，它默默记住了你还没处理的节点。

3. 非递归实现：用栈把递归翻译出来

递归版本虽然好写，但有两个实际问题：一是函数调用有额外开销，树很深时可能栈溢出；二是很多面试官会追问非递归怎么写，想看你是不是真的理解遍历过程。非递归的核心思路，是用一个显式的栈来模拟系统栈，把递归里“暂时挂起的节点”保存下来。

3.1 非递归先序：出栈即访问

void preorderIterative(TreeNode* root) { if (!root) return; stack<TreeNode*> st; st.push(root); while (!st.empty()) { TreeNode* cur = st.top(); st.pop(); cout << cur->val << " "; if (cur->right) st.push(cur->right); if (cur->left) st.push(cur->left); } }

这里有个很容易写反的细节：一定要先压右孩子，再压左孩子。为什么？因为栈是后进先出，右孩子先进栈会待在栈底，左孩子后进栈会待在栈顶，下一次循环先弹出左孩子，这样才能得到“根-左-右”的顺序。顺序一换，输出就变成“根-右-左”了，虽然程序不报错，但结果错得很隐蔽。这是我在面试题里见过最经典的“看似会做实际写错”的版本。

3.2 非递归中序：一路向左再回头

void inorderIterative(TreeNode* root) { stack<TreeNode*> st; TreeNode* cur = root; while (cur || !st.empty()) { while (cur) { st.push(cur); cur = cur->left; } cur = st.top(); st.pop(); cout << cur->val << " "; cur = cur->right; } }

中序没有先序那么直接，因为中序要先处理左子树，所以你得先“一路向左”，把沿途节点全部入栈，直到 cur 变成 nullptr，说明最左边走到底了。此时弹出栈顶节点并输出，然后让 cur 指向它的右子树，继续循环。

用测试树推演开头几步：cur=1，1 入栈，cur=2；2 入栈，cur=4；4 入栈，cur=nullptr。第一次 pop 出来的是 4，输出 4，cur=4->right（nullptr）。接着再 pop 出来 2，输出 2，cur=5。5 入栈后 cur 又走到 nullptr，再 pop 输出 5。你看，这个“一路向左再回头”的过程，正好等价于递归里“把左子树整个处理完再回来”。空树的情况也不用担心，while (cur || !st.empty())条件里 cur 为 nullptr、栈为空时循环直接跳过，自然不会有输出。

3.3 非递归后序：双栈法和标记法

后序是三种里最容易卡壳的。问题在于先序和中序只需要在“往下走”的时候入栈，回来的时候输出就行；后序要求左右子树都处理完再输出，单靠一个栈很难判断当前节点到底是被“路过”，还是终于可以输出了。这里给两种我实际用下来最顺手的写法。

方法一：双栈法（先序变种+反转）。

void postorderIterative(TreeNode* root) { if (!root) return; stack<TreeNode*> st1; stack<TreeNode*> st2; st1.push(root); while (!st1.empty()) { TreeNode* cur = st1.top(); st1.pop(); st2.push(cur); if (cur->left) st1.push(cur->left); if (cur->right) st1.push(cur->right); } while (!st2.empty()) { cout << st2.top()->val << " "; st2.pop(); } }

注意这个循环里入栈顺序和先序相反：先压左、再压右。于是 st1 弹出的顺序是“根-右-左”，也就是先序的镜像顺序。每次弹出的节点我们都压进 st2，最后再把 st2 整体弹出，由于 LIFO，“根右左”反着出来就是“左右根”，正好是后序。这个方法优点是代码短、不容易错，缺点是用了两个栈。面试时如果只要求写非递归后序，我一般先写这个，稳妥。

方法二：标记法（一个栈+visited 标志）。

void postorderIterative2(TreeNode* root) { stack<pair<TreeNode*, bool>> st; st.push({root, false}); while (!st.empty()) { auto [cur, visited] = st.top(); st.pop(); if (!cur) continue; if (visited) { cout << cur->val << " "; } else { st.push({cur, true}); // 当前节点标记已访问 st.push({cur->right, false}); st.push({cur->left, false}); } } }

每个节点第一次从栈里弹出时 visited 为 false，说明只是路过，把它标记为 true 后重新入栈，同时把左、右孩子入栈。栈是 LIFO，谁后入谁先出，所以想让左孩子先被处理，就要把左孩子最后入栈，于是代码里写入栈顺序是 cur、right、left，实际处理顺序就是 left、right、cur，完全符合后序。当 cur 第二次弹出时 visited 为 true，说明它的左右子树一定已经处理完了，这时候才输出。

注意：这个入栈顺序和处理顺序是反的。看到st.push({cur, true})先执行，别以为当前节点会先被处理，它反而会等 right 和 left 都从栈里弹出并处理完之后才轮到。这种“反直觉”正是标记法容易看迷糊的原因。

方法二比双栈法更贴近递归的本质，只需要一个栈，但每个节点会入栈两次，压栈次数多一倍。两种写法我都建议敲一遍，敲完你会对“递归隐式栈”有非常直观的感受。如果面试官继续问“能不能用一个栈且不用额外标记实现后序”，那种写法也有，但阅读性和稳定性都一般，不建议优先展示。

4. 层序遍历：从 DFS 跳到 BFS

前三种遍历都属于深度优先（DFS），核心是沿着一条分支走到底再回头；层序遍历则是广度优先（BFS），逐层往下扫。很多讨论里会提到“按层遍历”“层序遍历”，这里顺手讲掉，也方便你把它和前面三种放在一起对比。

4.1 队列实现按层扫描

void levelOrder(TreeNode* root) { if (!root) return; queue<TreeNode*> q; q.push(root); while (!q.empty()) { TreeNode* cur = q.front(); q.pop(); cout << cur->val << " "; if (cur->left) q.push(cur->left); if (cur->right) q.push(cur->right); } }

队列保证先进先出，所以同一层从左到右依次扩展，先处理到的节点，它的孩子也会先被处理，这样就实现了按层推进。对测试树输出是 1 2 3 4 5 6。注意层序并不是三种遍历之一，它是另一种维度上的遍历方式。

面试题里经常会出现“按层输出二叉树，每层放一个数组”的变体，做法是在 while 循环里先记下当前队列长度size = q.size()，然后连续弹出 size 个节点，把这些节点单独作为一层收集起来，再进入下一层。这个技巧在很多“之字形打印”“按层统计节点数”的题目里都能复用。

4.2 DFS 与 BFS 的选型对比

四种遍历用哪个，取决于你要解决什么问题。我把常见场景列个表：

空间复杂度上也值得记一下：DFS 的栈空间取决于树高 h，最坏是 O(h)；层序 BFS 的空间取决于某一层的最大节点数，最坏是 O(w)。对于一棵完全二叉树，BFS 的空间通常更可控；对于斜树，DFS 深一点但仍能用，BFS 反而要维护较宽的队列。没有绝对好坏，按场景选。

5. 高频翻车现场与排查手册

带过不少新同事，也看过很多刷题群里的提问，二叉树遍历的翻车点来来回回就那么几个。下面整理成速查，遇到问题直接对着查。

5.1 编译和运行错误速查表

另外补一句环境的事：VS Code 里写 C++ 如果连“hello world”都跑不起来，多半是 tasks.json 和 launch.json 没配好，不是遍历代码的问题。我建议先用命令行把编译器调通，再回到二叉树遍历上，否则环境问题和代码问题混在一起，特别浪费精力。

5.2 顺序全错但不报错的隐蔽陷阱

最坑的错误不是崩溃，而是程序跑得很欢，结果却是错的。比如后序标记法，如果忘了把 visited 标志重新入栈，写成了这样：

// 错误示范：结果其实是先序遍历 void postorderWrong(TreeNode* root) { stack<pair<TreeNode*, bool>> st; st.push({root, false}); while (!st.empty()) { auto [cur, visited] = st.top(); st.pop(); if (!cur) continue; cout << cur->val << " "; // 错！第一次经过就输出 st.push({cur->right, false}); st.push({cur->left, false}); } }

这段代码对测试树输出的是 1 2 4 5 3 6，也就是先序结果。程序不会崩，也不报错，但遍历逻辑完全不对。所以做题时只把“能跑出结果”当通过是不够的，一定要拿几棵不同的树对比标准输出，才能发现这种隐蔽错误。

注意：程序不报错不代表写对了。每次改完遍历，至少拿一棵非满二叉树验证输出顺序，比如上面那棵测试树，就能暴露大多数“错序但能跑”的问题。

5.3 三个自测方法，确认遍历写对了

1. 手算一棵固定树：用上面那棵测试树，先把期望结果写在本子上，程序输出和你手写的一致，基本说明当前实现没问题。
2. 交叉验证：学过“前序+中序可以唯一确定一棵二叉树”之后，你可以把程序生成的先序和中序拿来回推树，看能不能还原出原树；推不出来，遍历大概率有问题。
3. 边界测试：至少跑空树、只有根节点、只有左子树的斜树、只有右子树的斜树、完全二叉树这五组。很多人只在满二叉树上测试，结果斜树上出了 bug 都不知道。

边界测试里有两组非常值得注意：只有左子树的链 1-2-3，先序是 1 2 3，中序是 3 2 1，后序也是 3 2 1；只有右子树的链 1-2-3，先序是 1 2 3，中序是 1 2 3，后序是 3 2 1。看到中序在不同形态下会剧烈变化，你就会理解为什么“先左后右”的分支处理对中序影响这么大。

最后说点实在的。我带新人时发现，非递归后序是很多人卡得最久的地方，一卡就是一下午。其实它没有玄学，核心就一句话：递归帮你隐藏了栈的细节，非递归只是把这个栈显式地写出来。你先手动走几遍上面那棵小树，再把代码敲三遍，基本就能形成肌肉记忆。学完之后，我建议顺手把 LeetCode 144、94、145 和 102 四道题做了，做完你会觉得二叉树遍历真的很死板——只要套路对了，剩下的就是体力活。如果你在验证过程中发现自己的遍历结果和参考值对不上，优先检查三个地方：递归边界有没有判空、输出语句的位置、非递归里栈的压入顺序，九成问题都出在这三个地方。