树的遍历，在GESP六级大纲里就像是树这个章节的“敲门砖”。我带过的很多学生，最初都觉得不过就是三种递归写法嘛，背下来就完了，结果到了考场上，一道“已知中序和后序，让你求前序”直接傻眼，或者被要求“用非递归实现中序遍历”时，卡在第二个 while 循环里出不来。其实树的遍历远不止“背模板”这么简单——它牵扯到递归序的理解、栈的模拟，以及遍历序列之间的换算逻辑，而这些恰恰是六级考试反复设坑的地方。这篇文章我就从带学生刷六级的实际经验出发，把树的遍历从原理到代码再到考题套路完整走一遍，不管你是刚开始学树，还是已经写过不少遍历代码但总在某些变体上翻车，都应该有收获。
1. GESP六级里的树的遍历：考到什么程度才算过关
很多同学对“树的遍历”有一个错觉：我会写递归，会写层序，就够了。但六级考纲里对树的要求，远不止“会输出序列”这么简单。先弄明白考试边界，复习才不会跑偏。
1.1 六级考纲中“树”的知识边界
GESP 的级别体系是一级到八级递进的。五级已经考过递归、栈、队列的基础应用，到了六级，树第一次作为正式的数据结构登场，同时栈和递归也要进入“组合使用”的阶段。也就是说，树的遍历在六级里承担了一个双重身份：
- 它是树这个数据结构的入门动作，前序、中序、后序、层序，每一种遍历都是后续所有树算法（包括二叉搜索树操作、堆、并查集里的树形结构、图论里的 DFS/BFS）的底层动作；
- 它又是“栈的进阶应用”的天然载体。递归遍历底层是系统栈，非递归遍历就是手动栈。六级对“栈”的要求不满足于“会用栈做括号匹配”，而是要在树这种非线性结构上，体会栈的模拟过程。
所以你在复习时，不能只盯着“遍历输出”，要把“递归改迭代”和“由序列还原树”这两类题型当成重点。它们在六级卷面上通常以程序阅读、完善程序和算法设计题的形式出现，往往是拉开分数差距的地方。
1.2 真题里的常见考察形态
从近几年各级别卷子的风格来看，树的遍历在六级里大概有四种出法：
| 出题形态 | 典型考法 | 常见失分点 |
|---|---|---|
| 概念选择题 | 给一棵树，求先/中/后序序列 | 节点多时递归序理不清 |
| 程序阅读题 | 给一段递归或非递归代码，手算输出 | 没考虑空节点处理 |
| 完善程序题 | 补全非递归遍历的栈操作代码 | 压栈顺序写反 |
| 综合应用题 | 已知中序+前序/后序，还原二叉树 | 不清楚为什么必须要有中序 |
如果你已经刷过早期的级别卷子，会发现三级、四级偶尔也会以小题形式出现“二叉树前序序列是……”这种选择题，但那只是概念层。六级的要求是：给你两种遍历序列，你能把树还原出来；给你递归代码，你能改成非递归版本。这就不是背模板能解决的了。
2. 递归序：理解前中后序遍历的第一性原理
先问一个问题：为什么递归遍历那么难背？因为很多人把“前序=根左右、中序=左根右、后序=左右根”当成三条独立的规则在背，背完就忘，换棵树就乱。实际上，三种递归遍历在代码层面几乎一模一样，唯一的区别是打印语句放在哪个位置。
2.1 三个访问时机：为什么“前中后”只是打印位置不同
看下面这段代码，我建议你把它当成一个整体来记：
struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; void traverse(TreeNode* root) { if (root == nullptr) return; // 位置 A：第一次来到这个节点 cout << root->val << " "; // 先序 traverse(root->left); // 位置 B：左子树处理完，回到这个节点 cout << root->val << " "; // 中序 traverse(root->right); // 位置 C：右子树处理完，最后一次回到这个节点 cout << root->val << " "; // 后序 }注意，同一个节点在递归过程中会被“经过”三次：第一次是刚进入函数时，第二次是左子树返回后，第三次是右子树返回后。你决定在哪个时机打印，输出就是哪种遍历。所谓“前序、中序、后序”，指的是根节点的访问时机——先访问根，叫前序；左子树之后访问根，叫中序；左右子树都处理完才访问根，叫后序。
2.2 用“递归序”把遍历顺序变成直觉
理解了三次经过之后，我再给你一个非常好用的工具：把整棵树的递归序完整写出来。以一课经典二叉树为例：
1 / \ 2 3 / \ 4 5从根节点出发，完整走一遍递归过程（碰到空节点就返回），每个非空节点会被记录三次，得到的递归序是：
1, 2, 4, 4, 4, 2, 5, 5, 5, 2, 1, 3, 3, 3, 1
- 第一次遇到节点时打印 → 先序：
1 2 4 5 3 - 第二次遇到节点时打印 → 中序：
4 2 5 1 3 - 第三次遇到节点时打印 → 后序：
4 5 2 3 1
这个递归序的价值在于：它把“根左右”“左根右”这种抽象口诀还原成了具体的执行过程。你在考场上一旦紧张，不用去背口诀，只要在脑子里过一遍递归的调用与返回，顺序自然就出来了。我带学生时，要求他们能手写出任意一课不超过 15 个节点的二叉树的递归序，写熟了，前中后序遍历基本就不会再错。
2.3 边界条件：空节点是递归的命门
递归遍历还有一个特别容易被忽略的细节：if (root == nullptr) return;这一行到底能不能省？
省了会怎样？递归会无限调用下去，直到栈溢出。因为一个没有子节点的叶子节点，它的 left 和 right 都是 nullptr，递归函数拿到 nullptr 后没有终止条件，就会继续访问 nullptr->left，直接段错误或崩溃。很多同学手写递归时能写对，程序填空时却总在这一行上犹豫——实际上这一行是三种遍历的共同前提，缺少它，位置 A/B/C 的打印逻辑全都不成立。
另外，处理只有一个孩子的节点也要小心。比如节点只有左孩子没有右孩子，中序遍历时，左子树处理完，会经过位置 B 打印，然后递归右子树，右子树参数是 nullptr，函数直接返回，流程结束。这个“空右子树”的返回动作，初学者往往在脑内模拟时直接跳过，导致手算中序结果出错。记住：空节点也是递归过程的一部分，在递归序里它代表着“无中生有又归于无”的边界。
3. 递归改迭代：考场上真正拉开差距的地方
GESP 六级有一个明确导向：你要能理解递归背后的机制，而不是只会调用递归。于是“非递归遍历”成了高频考点。先想清楚它为什么重要，你才知道怎么练。
3.1 考纲为什么非要考非递归遍历
递归的本质是系统栈的自动压栈与弹栈。系统栈帮你保存了每一层调用的局部信息和返回地址，所以递归代码才能写得那么简洁。但系统栈有两个局限：
- 深度受限。树退化成链表时（比如一棵只有右子节点的树），n 个节点的深度就是 n，递归深度超过系统栈上限会爆栈；
- 不透明。你在代码里看不到“压栈、弹栈”的过程，遇到需要中途改变遍历顺序的变体题（比如从叶子反向遍历、按之字形层序遍历），没有栈的概念就寸步难行。
六级要求“理解栈的应用”，树、图领域里最经典的栈应用就是非递归遍历。考递归改迭代，本质上是考察你对“递归调用过程”的理解程度。
3.2 先序和中序迭代：两个最容易搞混的写法
先说先序。先序的访问顺序是“根左右”，手动用栈模拟时，思路很直接：根节点先访问，访问完压右孩子，再压左孩子。因为栈是后进先出，想要左孩子先被弹出，就得先压右。
void preorderIter(TreeNode* root) { stack<TreeNode*> st; if (root) 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); } }中序就不一样了。中序是“左根右”，你没法一到节点就访问，得先把整条左链全部压栈，直到没有左孩子，然后再弹栈访问，转去处理右子树：
void inorderIter(TreeNode* root) { stack<TreeNode*> st; TreeNode* cur = root; while (cur != nullptr || !st.empty()) { while (cur != nullptr) { // 一路向左，压到底 st.push(cur); cur = cur->left; } cur = st.top(); // 弹出最左节点 st.pop(); cout << cur->val << " "; cur = cur->right; // 转向右子树 } }很多人把这两个写法搞混，核心原因是没想明白一个关键区别：先序为什么可以直接“遇到就访问”？因为访问根节点永远发生在处理左右子树之前，所以根出栈即访问即可，子树的顺序交给栈去调度。而中序必须先把根“挂账”在栈里，等左子树彻底处理完，才能翻出来访问根。
3.3 后序迭代：双栈法最不容易出错
后序“左右根”的手动模拟是最麻烦的。麻烦在于：当你从栈里弹出某个节点时，你分不清它的左子树和右子树到底处理完没有。很多同学在考场上写后序迭代，写一半就绕晕，要么把节点访问了两次，要么左右顺序反了。
考场推荐双栈解法，思路巧妙但好记：
- 先序的流程是“根左右”，如果把压栈顺序反过来（先压左再压右），得到的是“根右左”；
- 后序“左右根”正好是“根右左”的逆序；
- 所以用第一个栈做出“根右左”的输出顺序，压进第二个栈，最后把第二个栈整体弹出。
void postorderIter(TreeNode* root) { stack<TreeNode*> st1, st2; if (root) 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(); } }理解这个解法后，我建议你在草稿纸上手动跑一遍 2.2 节那棵二叉树，确认 st2 里的顺序依次是4 5 2 3 1。这个验证过程本身就是在复习“先序改写”的思维，比死记代码牢固得多。
3.4 颜色标记法：一套模板通吃三种遍历
如果你在考场上压力大，担心三种迭代写法记串，我还有一个后备方案：颜色标记法。它用一个pair<TreeNode*, bool>，bool 表示这个节点“是否已经可以作为结果输出”。第一次入栈时标记为 false，等它的左右子树都安排好了，再一次入栈标记为 true，轮到它时就输出。
void traversal(TreeNode* root, int mode) { // mode: 0=先序, 1=中序, 2=后序 stack<pair<TreeNode*, bool>> st; st.push({root, false}); while (!st.empty()) { auto [node, visited] = st.top(); st.pop(); if (node == nullptr) continue; if (visited) { cout << node->val << " "; } else { if (mode == 0) { // 先序：根左右 st.push({node->right, false}); st.push({node->left, false}); st.push({node, true}); } else if (mode == 1) { // 中序：左根右 st.push({node->right, false}); st.push({node, true}); st.push({node->left, false}); } else { // 后序：左右根 st.push({node, true}); st.push({node->right, false}); st.push({node->left, false}); } } } }压栈顺序和输出顺序一定是相反的，这是理解这个模板的唯一关键。你不需要分别记三套循环，只需要记住“后进先出”，再根据输出顺序从后往前推压栈顺序。这种写法牺牲了一点常数时间，但换来了极高的稳定性，我个人认为在考试场景里非常划算。
4. 由遍历序列还原二叉树：六级最经典的保分题
如果说非递归遍历是程序填空题的常客，那“还原二叉树”就是综合题里的钉子户。先序、中序、后序三个序列，任取两个，能不能唯一还原一棵二叉树？结论是：必须包含中序序列，否则不行。下面拆开讲。
4.1 已知中序+前序：核心是“找根，切区间”
思路一句话就能说清：前序的第一个节点一定是整棵树的根；拿这个根去中序序列里定位，根左边是左子树的中序序列，根右边是右子树的中序序列；前序序列里紧跟在根后面、长度等于左子树节点数的那一段，就是左子树的前序序列，再往后是右子树的前序序列。递归处理即可。
unordered_map<int, int> pos; TreeNode* buildFromPre(vector<int>& pre, vector<int>& in, int preL, int preR, int inL, int inR) { if (preL > preR) return nullptr; int rootVal = pre[preL]; TreeNode* root = new TreeNode(rootVal); int k = pos[rootVal]; // 根在中序中的位置 int leftSize = k - inL; // 左子树节点个数 root->left = buildFromPre(pre, in, preL + 1, preL + leftSize, inL, k - 1); root->right = buildFromPre(pre, in, preL + leftSize + 1, preR, k + 1, inR); return root; }我特别提醒一个细节：leftSize = k - inL，而不是k。因为 inL 不一定永远是 0，递归进入右子树后，中序区间起点会右移。这个leftSize是前序区间切割的唯一依据，算错一个 +1 或 -1，整棵树的左右子树就全错位了。
4.2 已知中序+后序：逻辑完全镜像，根移到了末尾
中序+后序的思路一模一样，唯一的区别是：后序序列的最后一个节点是根。根在中序中定位后，左子树节点数依然用k - inL计算，然后切割中序区间和后序区间。
TreeNode* buildFromPost(vector<int>& post, vector<int>& in, int postL, int postR, int inL, int inR) { if (postL > postR) return nullptr; int rootVal = post[postR]; // 后序最后一个元素是根 TreeNode* root = new TreeNode(rootVal); int k = pos[rootVal]; int leftSize = k - inL; root->left = buildFromPost(post, in, postL, postL + leftSize - 1, inL, k - 1); root->right = buildFromPost(post, in, postL + leftSize, postR - 1, k + 1, inR); return root; }两个算法放在一起看就是一对镜像操作。如果你把 4.1 的边界彻底搞懂了，4.2 只需要把“根取 pre[preL]”改成“根取 post[postR]”，同时把后序的右子树区间右端点改成postR - 1，其他全部照搬。
4.3 为什么必须要有中序：前序+后序无法唯一确定树
这是六级选择题里一个很爱考的陷阱：单独给前序和后序，能不能还原唯一二叉树？
答案是不能。原因在于，当前序和后序都确定时，你只能确定“谁是根”，但无法区分“某个节点到底是左孩子还是右孩子”。最经典的例子：一棵只有根节点 1 和左孩子 2 的二叉树，前序是1 2，后序是2 1；一棵只有根节点 1 和右孩子 2 的二叉树，前序也是1 2，后序也是2 1。所以同一个前序+后序组合，可能对应多棵不同的树。
理解这一点，你就会明白为什么还原树的两道经典题都强制要求“中序+另一个序列”——中序的唯一作用是告诉你：根在哪，左右子树的分界线就在哪。没有这条分界线，树的形态就无法锁定。
4.4 实现里的两个大坑：哈希映射与区间边界
先报第一个坑：不要在递归里用循环找根的位置。如果每层递归都扫一遍中序数组，总复杂度会退化成 O(n²)，n 达到 10^5 级别就危险了。正确做法是预处理一个哈希表，把中序序列中每个值对应的下标存下来，之后每层递归 O(1) 定位：
for (int i = 0; i < n; i++) { pos[in[i]] = i; }第二个坑是区间边界。我在 4.1 里特别强调过leftSize的计算。如果你不确定自己的边界写对没有，我教你一个验证方法：在递归函数入口打印preL, preR, inL, inR，用一棵小树手动核对每一层参数的变化。带学生时，我见过太多人栽在“左子树的右边界应该是 preL+leftSize 还是 preL+leftSize+1”这种问题上，自己验证一遍，比对着答案改十遍都强。
5. 从遍历到应用：层序、深度与树的直径
前中后序遍历属于深度优先的思路，接下来是广度优先的层序遍历，以及两个非常依赖遍历思想的经典应用。这几块是六级里把“树的遍历”从基础概念引向算法思维的关键路径。
5.1 层序遍历模板与“分层统计”变体
层序遍历就是广度优先搜索（BFS）在树上的直接体现，核心数据结构是队列：根节点入队，然后每弹出一个节点，就把它的左右孩子依次入队。
void levelOrder(TreeNode* root) { queue<TreeNode*> q; if (root) q.push(root); while (!q.empty()) { int sz = q.size(); // 当前层的节点数 for (int i = 0; i < sz; i++) { TreeNode* cur = q.front(); q.pop(); cout << cur->val << " "; if (cur->left) q.push(cur->left); if (cur->right) q.push(cur->right); } cout << endl; // 每层结束换行 } }这里的sz = q.size()是分层统计的关键。如果你不用 sz 固定当前层大小，而是直接while (!q.empty())一路弹到底，所有节点会被当成同一层输出，那就没法做“每层求和”“每层最大值”“之字形层序遍历”这些变体题了。
层序遍历还有一个重要的定性区别：它和前中后序遍历不同，它不提供“某个节点的中序位置”这样的结构性信息，所以不能单独用来还原二叉树。这一点在概念选择题里偶尔会出现，记住即可。
5.2 递归求深度与栈溢出的现实风险
树的深度是树的遍历思想最直接的产物。递归写法一行就能搞定：
int maxDepth(TreeNode* root) { if (root == nullptr) return 0; return max(maxDepth(root->left), maxDepth(root->right)) + 1; }这个递归本身也是后序思想：先拿到左子树深度、右子树深度，再汇总加一。但我要提醒一个现实问题：当树退化成链表形态（最坏情况是一棵只有右孩子的斜树），递归深度会等于节点数 n。在竞赛环境或大数据的输入下，n 到达 10^5 甚至 10^6 时，系统栈可能直接爆掉。
六级考场上通常不会拿 10^6 的数据卡你，但你得养成一个意识：凡是树退化成链可能导致递归深度过大的题目，就该考虑用层序遍历求深度。层序天然是迭代的，不消耗系统栈，代码也不复杂——每走一层 depth 加一，直到队列清空。
5.3 树的直径：把遍历思维用到极致
树的直径是指树上最远两个节点之间的距离（边的数量）。这个题的标准解法是两遍 DFS：第一遍从任意节点出发找到最远点 A，第二遍从 A 出发找到最远点 B，A 到 B 的距离就是直径。但更体现“遍历思想”的是一遍后序遍历的写法：
int diameter = 0; int dfs(TreeNode* root) { if (root == nullptr) return 0; int L = dfs(root->left); int R = dfs(root->right); diameter = max(diameter, L + R); // 经过当前节点的最长路径 return max(L, R) + 1; // 返回当前节点的最大高度 }核心思路是：直径一定经过某个节点，等于该节点左子树最大高度加右子树最大高度。所以每个节点都要做两件事——先递归拿到左右子树的高度（后序），再用这两个高度更新全局答案。这种“先处理子树，再汇总信息”的模式，正是后序遍历在算法设计层面的真正威力。很多七级、八级要考的树上动态规划，本质上就是这个模式加上状态设计。学树的遍历时顺手把这个思想理解透，后面的路会顺畅很多。
带学生复习到这一块时，我经常说一句话：树的遍历不是背四个模板就完事，它是一个“递归序理解 → 栈模拟 → 序列换算 → 信息汇总”的完整链条。如果你正在准备六级，我的建议是别急着上手刷题，先拿张白纸，把那棵经典的二叉树反复画递归序，画到闭上眼都能说出每个节点第几次被经过，再去碰非递归和还原树的题目。凡是这一步做得扎实的学生，后面学堆、学并查集、学图遍历基本都顺风顺水；凡是跳过这一步直接背代码的，多半过段时间还要回头补课。树的遍历就这么点东西，但把它真正吃透的人，等于提前拿到了通往六级后面所有树相关考点的钥匙。
