树的遍历在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) { stackTreeNode* 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) { stackTreeNode* 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) { stackTreeNode* 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 颜色标记法一套模板通吃三种遍历如果你在考场上压力大担心三种迭代写法记串我还有一个后备方案颜色标记法。它用一个pairTreeNode*, boolbool 表示这个节点“是否已经可以作为结果输出”。第一次入栈时标记为 false等它的左右子树都安排好了再一次入栈标记为 true轮到它时就输出。void traversal(TreeNode* root, int mode) { // mode: 0先序, 1中序, 2后序 stackpairTreeNode*, 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_mapint, int pos; TreeNode* buildFromPre(vectorint pre, vectorint 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(vectorint post, vectorint 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用一棵小树手动核对每一层参数的变化。带学生时我见过太多人栽在“左子树的右边界应该是 preLleftSize 还是 preLleftSize1”这种问题上自己验证一遍比对着答案改十遍都强。5. 从遍历到应用层序、深度与树的直径前中后序遍历属于深度优先的思路接下来是广度优先的层序遍历以及两个非常依赖遍历思想的经典应用。这几块是六级里把“树的遍历”从基础概念引向算法思维的关键路径。5.1 层序遍历模板与“分层统计”变体层序遍历就是广度优先搜索BFS在树上的直接体现核心数据结构是队列根节点入队然后每弹出一个节点就把它的左右孩子依次入队。void levelOrder(TreeNode* root) { queueTreeNode* 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 出发找到最远点 BA 到 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; // 返回当前节点的最大高度 }核心思路是直径一定经过某个节点等于该节点左子树最大高度加右子树最大高度。所以每个节点都要做两件事——先递归拿到左右子树的高度后序再用这两个高度更新全局答案。这种“先处理子树再汇总信息”的模式正是后序遍历在算法设计层面的真正威力。很多七级、八级要考的树上动态规划本质上就是这个模式加上状态设计。学树的遍历时顺手把这个思想理解透后面的路会顺畅很多。带学生复习到这一块时我经常说一句话树的遍历不是背四个模板就完事它是一个“递归序理解 → 栈模拟 → 序列换算 → 信息汇总”的完整链条。如果你正在准备六级我的建议是别急着上手刷题先拿张白纸把那棵经典的二叉树反复画递归序画到闭上眼都能说出每个节点第几次被经过再去碰非递归和还原树的题目。凡是这一步做得扎实的学生后面学堆、学并查集、学图遍历基本都顺风顺水凡是跳过这一步直接背代码的多半过段时间还要回头补课。树的遍历就这么点东西但把它真正吃透的人等于提前拿到了通往六级后面所有树相关考点的钥匙。
树的遍历在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) { stackTreeNode* 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) { stackTreeNode* 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) { stackTreeNode* 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 颜色标记法一套模板通吃三种遍历如果你在考场上压力大担心三种迭代写法记串我还有一个后备方案颜色标记法。它用一个pairTreeNode*, boolbool 表示这个节点“是否已经可以作为结果输出”。第一次入栈时标记为 false等它的左右子树都安排好了再一次入栈标记为 true轮到它时就输出。void traversal(TreeNode* root, int mode) { // mode: 0先序, 1中序, 2后序 stackpairTreeNode*, 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_mapint, int pos; TreeNode* buildFromPre(vectorint pre, vectorint 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(vectorint post, vectorint 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用一棵小树手动核对每一层参数的变化。带学生时我见过太多人栽在“左子树的右边界应该是 preLleftSize 还是 preLleftSize1”这种问题上自己验证一遍比对着答案改十遍都强。5. 从遍历到应用层序、深度与树的直径前中后序遍历属于深度优先的思路接下来是广度优先的层序遍历以及两个非常依赖遍历思想的经典应用。这几块是六级里把“树的遍历”从基础概念引向算法思维的关键路径。5.1 层序遍历模板与“分层统计”变体层序遍历就是广度优先搜索BFS在树上的直接体现核心数据结构是队列根节点入队然后每弹出一个节点就把它的左右孩子依次入队。void levelOrder(TreeNode* root) { queueTreeNode* 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 出发找到最远点 BA 到 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; // 返回当前节点的最大高度 }核心思路是直径一定经过某个节点等于该节点左子树最大高度加右子树最大高度。所以每个节点都要做两件事——先递归拿到左右子树的高度后序再用这两个高度更新全局答案。这种“先处理子树再汇总信息”的模式正是后序遍历在算法设计层面的真正威力。很多七级、八级要考的树上动态规划本质上就是这个模式加上状态设计。学树的遍历时顺手把这个思想理解透后面的路会顺畅很多。带学生复习到这一块时我经常说一句话树的遍历不是背四个模板就完事它是一个“递归序理解 → 栈模拟 → 序列换算 → 信息汇总”的完整链条。如果你正在准备六级我的建议是别急着上手刷题先拿张白纸把那棵经典的二叉树反复画递归序画到闭上眼都能说出每个节点第几次被经过再去碰非递归和还原树的题目。凡是这一步做得扎实的学生后面学堆、学并查集、学图遍历基本都顺风顺水凡是跳过这一步直接背代码的多半过段时间还要回头补课。树的遍历就这么点东西但把它真正吃透的人等于提前拿到了通往六级后面所有树相关考点的钥匙。
