1. 项目概述为什么二叉树遍历是程序员的基本功如果你正在学习数据结构或者准备技术面试那么“二叉树的遍历”这个主题你一定绕不过去。它不仅是理解树形结构的基础更是后续学习二叉搜索树、平衡二叉树、堆等高级数据结构的敲门砖。很多朋友第一次接触这个概念时可能会被“前序”、“中序”、“后序”这些术语搞晕代码写着写着就乱了。我自己在初学以及后来带新人的过程中发现很多人卡壳的地方不在于记不住定义而在于无法将递归的思维过程可视化更不知道除了递归还有哪些更直观、更通用的方法。今天我们就来彻底拆解这个经典问题。我会用 C 带你实现二叉树的三种深度优先遍历前序、中序、后序并且不止步于递归。我们将深入探讨递归背后的函数调用栈原理并手把手实现迭代法让你真正理解每一步在做什么。最后我们还会对比这两种方法的优劣和适用场景并分享一些在笔试面试中常见的变形题和避坑技巧。无论你是刚入门的新手还是想巩固基础的老手这篇文章都能让你对二叉树遍历有一个清晰、深刻且实用的认识。2. 二叉树遍历的核心思路与递归实现在开始写代码之前我们必须先统一思想遍历的本质是什么遍历就是按照某种规则访问树中的每一个节点并且每个节点只访问一次。对于二叉树最经典的规则就是根据访问“根节点”的时机来定义。2.1 三种遍历方式的定义与记忆技巧首先我们明确一下三种遍历方式的定义。假设我们要处理一个节点这个操作可以是打印节点值、将值存入数组等我们统一称之为“访问”。前序遍历先访问根节点然后递归地前序遍历左子树再递归地前序遍历右子树。顺序是根 - 左 - 右。中序遍历先递归地中序遍历左子树然后访问根节点再递归地中序遍历右子树。顺序是左 - 根 - 右。后序遍历先递归地后序遍历左子树然后递归地后序遍历右子树最后访问根节点。顺序是左 - 右 - 根。怎么记关键就在“根”的位置。前序的“根”在最前中序的“根”在中间后序的“根”在最后。记住这一点定义就不会混淆。为了后续演示我们先定义一个简单的二叉树节点结构体这是所有操作的基础struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };2.2 递归实现最直观的代码表达递归实现是理解遍历逻辑最直接的方式因为它几乎就是遍历定义的代码直译。前序遍历的递归实现class Solution { public: vectorint preorderTraversal(TreeNode* root) { vectorint result; preorder(root, result); return result; } void preorder(TreeNode* node, vectorint res) { if (node nullptr) return; // 递归终止条件 res.push_back(node-val); // 访问根节点 preorder(node-left, res); // 遍历左子树 preorder(node-right, res); // 遍历右子树 } };中序遍历的递归实现void inorder(TreeNode* node, vectorint res) { if (node nullptr) return; inorder(node-left, res); // 遍历左子树 res.push_back(node-val); // 访问根节点 inorder(node-right, res); // 遍历右子树 }后序遍历的递归实现void postorder(TreeNode* node, vectorint res) { if (node nullptr) return; postorder(node-left, res); // 遍历左子树 postorder(node-right, res); // 遍历右子树 res.push_back(node-val); // 访问根节点 }注意递归代码非常简洁但它的核心在于“递归栈”。系统帮我们维护了一个隐式的调用栈。当执行preorder(node-left, res)时当前函数的状态变量、执行位置被压栈然后去处理左子节点。理解这一点是后面理解迭代法显式用栈的关键。2.3 递归的优缺点与适用场景优点代码极其简洁逻辑清晰与遍历定义完全对应不易出错。易于理解和教学是初学者掌握遍历概念的最佳途径。缺点存在栈溢出风险当二叉树深度非常大例如退化成一条链表时递归调用的层级过深可能超出系统栈的空间限制导致程序崩溃。效率开销每次函数调用都有一定的开销参数压栈、跳转等虽然对于现代编译器和普通问题来说影响不大但在极端性能敏感的场景下需要考虑。调试困难递归过程不如迭代直观在调试时跟踪多层调用栈状态比较麻烦。因此递归法适合在树深度可控、代码简洁性优先的场景下使用。但在面试或要求鲁棒性的生产代码中掌握迭代法通常是加分项。3. 迭代法实现用栈模拟递归过程迭代法的核心思想是自己用一个栈来模拟系统递归调用栈的过程。这样我们就拥有了对遍历过程的完全控制权也避免了递归的深度限制。这是本部分的重点和难点我会详细拆解每一步。3.1 前序遍历的迭代法实现前序遍历的顺序是“根左右”。迭代的思路是先把根节点压入栈。循环条件栈不为空。弹出栈顶节点并访问它根。因为栈是“后进先出”为了接下来先处理左子树我们需要先将右孩子压栈再将左孩子压栈。这样下次循环弹出时就会先弹出左孩子实现“左”先于“右”。vectorint preorderTraversal(TreeNode* root) { vectorint result; if (root nullptr) return result; stackTreeNode* stk; stk.push(root); // 初始化栈放入根节点 while (!stk.empty()) { TreeNode* node stk.top(); // 取出当前“根”节点 stk.pop(); result.push_back(node-val); // 访问 // 关键先右后左入栈 if (node-right) stk.push(node-right); if (node-left) stk.push(node-left); } return result; }实操心得很多同学在这里会弄反左右子节点的入栈顺序。你只需要记住我们的目标是让左子节点先被弹出访问。由于栈是LIFO后进先出后进去的左子节点会先出来所以我们要先压入右子节点再压入左子节点。画一个只有三个节点的小树手动模拟一下栈的变化立刻就明白了。3.2 中序遍历的迭代法实现中序遍历的顺序是“左根右”这是迭代法中最有挑战性的一种。难点在于访问节点根的时机是在其左子树全部处理完毕之后。我们不能像前序那样一遇到节点就访问。标准思路推荐掌握使用一个指针cur来指向当前待处理的节点用一个栈stk来保存暂时不访问的节点。外层循环条件cur不为空或栈不为空。这涵盖了两种情况正在深入左子树cur不为空或者需要回溯到之前的节点栈不为空。内层操作如果cur不为空说明还有左子树需要深入。将当前节点cur压栈注意此时不访问然后让cur指向其左孩子。重复此过程直到走到最左边。如果cur为空说明已经到达某条路径的最左端。此时需要回溯弹出栈顶节点这就是当前子树的“根”访问它。然后让cur指向这个被访问节点的右孩子开始处理右子树。vectorint inorderTraversal(TreeNode* root) { vectorint result; stackTreeNode* stk; TreeNode* cur root; while (cur ! nullptr || !stk.empty()) { // 一路向左将经过的节点都压入栈 if (cur ! nullptr) { stk.push(cur); cur cur-left; // 左 } else { // 到达最左边回溯 cur stk.top(); stk.pop(); result.push_back(cur-val); // 根 cur cur-right; // 转向右子树 } } return result; }这个算法非常精妙它完美模拟了递归中“深入左子树 - 返回 - 访问根 - 深入右子树”的过程。务必多模拟几遍。3.3 后序遍历的迭代法实现后序遍历的顺序是“左右根”。如果我们把前序遍历的“根左右”顺序稍作修改变成“根右左”然后将结果反转得到的就是“左右根”也就是后序遍历的结果。这是一种非常巧妙的“取巧”方法。方法一修改前序反转vectorint postorderTraversal(TreeNode* root) { vectorint result; if (root nullptr) return result; stackTreeNode* stk; stk.push(root); while (!stk.empty()) { TreeNode* node stk.top(); stk.pop(); result.push_back(node-val); // 访问“根” // 注意这里为了最终得到“左右根”前序修改版需按“先左后右”入栈 // 这样出栈顺序才是“根右左” if (node-left) stk.push(node-left); if (node-right) stk.push(node-right); } // 将“根右左”的结果反转得到“左右根” reverse(result.begin(), result.end()); return result; }方法二严格模拟后序访问顺序还有一种更直接但稍复杂的方法需要记录上一个访问的节点以判断右子树是否已处理完毕。这里提供代码供学有余力的朋友研究vectorint postorderTraversal(TreeNode* root) { vectorint result; stackTreeNode* stk; TreeNode* cur root; TreeNode* lastVisited nullptr; // 记录上一个被访问的节点 while (cur ! nullptr || !stk.empty()) { // 走到最左边 while (cur ! nullptr) { stk.push(cur); cur cur-left; } cur stk.top(); // 如果右子树为空或者右子树刚被访问过则可以访问当前节点 if (cur-right nullptr || cur-right lastVisited) { result.push_back(cur-val); stk.pop(); lastVisited cur; cur nullptr; // 当前子树处理完毕下一轮从栈中取新节点 } else { // 否则转向处理右子树 cur cur-right; } } return result; }对于面试和一般应用掌握“修改前序反转”的方法就足够了它写起来快不易错。第二种方法虽然更符合逻辑原意但边界条件需要小心处理。4. 莫里斯遍历一种空间复杂度O(1)的奇技我们上面讨论的迭代法虽然避免了递归调用栈但依然使用了一个显式的栈空间复杂度是 O(h)h 是树的高度。有没有可能只用常数空间即 O(1)完成遍历呢答案是肯定的这就是莫里斯遍历。它利用了二叉树中大量的空指针通过临时修改树的结构遍历后会恢复来实现。莫里斯遍历的核心思想是对于当前节点cur如果它有左子树则找到它左子树上的最右节点即中序遍历下cur的前驱节点pre。我们将这个最右节点pre的右指针指向当前的cur。这样当我们遍历完左子树后可以通过这个新加的指针回到cur节点。由于这部分算法理解起来有一定难度且在实际开发中较少要求我们以前序遍历为例简要说明其神奇之处vectorint preorderTraversal_Morris(TreeNode* root) { vectorint result; TreeNode* cur root; while (cur ! nullptr) { if (cur-left nullptr) { // 如果没有左孩子访问当前节点然后转向右孩子 result.push_back(cur-val); cur cur-right; } else { // 找到当前节点左子树的最右节点 TreeNode* pre cur-left; while (pre-right ! nullptr pre-right ! cur) { pre pre-right; } if (pre-right nullptr) { // 第一次到达建立线索并访问当前节点前序 pre-right cur; result.push_back(cur-val); // **前序访问点** cur cur-left; } else { // 第二次到达说明左子树已遍历完拆除线索 pre-right nullptr; cur cur-right; } } } return result; }注意事项莫里斯遍历会修改树的结构虽然在遍历结束后会恢复但在多线程环境或遍历过程中不允许修改树的场景下绝对不能用。它更像一种炫技的算法在面试中提一下能展示你的深度但实际编码中递归和显式栈的迭代法才是王道。5. 层序遍历广度优先的视角虽然标题是“三种遍历”通常指深度优先的前中后序但谈到树的遍历层序遍历绝对是不可或缺的一部分。它属于广度优先搜索使用队列实现能让我们按层来观察树的结构。层序遍历的标准实现vectorvectorint levelOrder(TreeNode* root) { vectorvectorint result; if (root nullptr) return result; queueTreeNode* q; q.push(root); while (!q.empty()) { int levelSize q.size(); // 当前层的节点数 vectorint currentLevel; for (int i 0; i levelSize; i) { TreeNode* node q.front(); q.pop(); currentLevel.push_back(node-val); if (node-left) q.push(node-left); if (node-right) q.push(node-right); } result.push_back(currentLevel); } return result; }为什么需要levelSize这是一个关键技巧。在进入每一层的循环前先记录当前队列的长度这个长度就是这一层节点的数量。然后我们只弹出这么多节点进行处理这样就能严格区分每一层的输出。如果不这样做队列中会混合不同层的节点无法实现分层存储。层序遍历的应用非常广泛例如求树的深度、找每层最大值、判断是否是完全二叉树等。6. 常见问题与实战排查技巧在实际编码和面试中单纯写对遍历代码只是第一步。下面这些衍生问题和易错点才是真正考验理解深度的地方。6.1 如何根据两种遍历序列重建二叉树这是一个经典问题。结论是必须要有中序遍历序列。已知前序中序可以唯一确定一棵二叉树。已知后序中序也可以唯一确定一棵二叉树。但是已知前序后序不能唯一确定一棵二叉树除非是真二叉树即每个节点都有0或2个子节点。重建的核心思路以前序中序为例前序序列的第一个元素一定是整棵树的根节点。在中序序列中找到这个根节点其左侧就是左子树的中序序列右侧就是右子树的中序序列。根据左子树节点数量可以在前序序列中划分出左子树的前序序列和右子树的前序序列。对左右子树递归地进行上述过程。TreeNode* buildTree(vectorint preorder, vectorint inorder) { if (preorder.empty()) return nullptr; // 构建哈希映射快速定位中序序列中根节点的位置 unordered_mapint, int indexMap; for (int i 0; i inorder.size(); i) { indexMap[inorder[i]] i; } return helper(preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1, indexMap); } TreeNode* helper(vectorint preorder, int pStart, int pEnd, vectorint inorder, int iStart, int iEnd, unordered_mapint, int indexMap) { if (pStart pEnd || iStart iEnd) return nullptr; int rootVal preorder[pStart]; TreeNode* root new TreeNode(rootVal); int rootIndexInInorder indexMap[rootVal]; int leftSubtreeSize rootIndexInInorder - iStart; // 递归构建左子树 root-left helper(preorder, pStart 1, pStart leftSubtreeSize, inorder, iStart, rootIndexInInorder - 1, indexMap); // 递归构建右子树 root-right helper(preorder, pStart leftSubtreeSize 1, pEnd, inorder, rootIndexInInorder 1, iEnd, indexMap); return root; }6.2 迭代法写中序遍历时为什么我的代码会死循环或漏节点这通常是循环条件或指针更新逻辑有误。请对照检查以下几点循环条件必须是while (cur ! nullptr || !stk.empty())。两者是“或”的关系缺一不可。如果只写!stk.empty()在初始cur指向根节点时无法进入“向左深入”的流程。如果只写cur ! nullptr当左子树遍历完需要从栈回溯时循环会提前结束。指针更新时机在if (cur ! nullptr)分支里压栈后一定要执行cur cur-left让指针向深处移动。在else分支里访问完栈顶节点后一定要执行cur cur-right将当前指针指向右子树无论右子树是否为空。如果忘记这一步cur会一直为nullptr导致不断从栈中弹出同一个节点造成逻辑错误。栈操作顺序一定是先push(cur)再cur cur-left。顺序反了就会丢失当前节点。6.3 如何直观地验证遍历代码的正确性不要只靠脑子想最好的方法是构造一棵简单的测试树例如根节点为1左孩子为2右孩子为3。手动推导遍历结果前序1 - 2 - 3中序2 - 1 - 3后序2 - 3 - 1运行你的代码看输出是否匹配。构造更复杂的树例如节点1(2(4,5),3(,6))。再手动计算和程序比对。考虑边界条件空树、只有根节点的树、只有左子树的树退化成链表、只有右子树的树。6.4 在遍历过程中除了保存值还能做什么遍历的框架是通用的访问节点时的“操作”可以是任何事。这打开了解决无数问题的大门计算节点数访问时计数器加一。计算树的高度后序遍历返回左右子树高度的最大值加一。判断平衡二叉树在后序遍历中同时计算高度并判断左右子树高度差。寻找最大路径和后序遍历计算经过当前节点的最大路径和。序列化与反序列化以前序遍历为例访问时将节点值和空指针标记存入字符串。一个经典例子求二叉树的最大深度后序遍历思想int maxDepth(TreeNode* root) { if (root nullptr) return 0; int leftDepth maxDepth(root-left); // 遍历左 int rightDepth maxDepth(root-right); // 遍历右 return max(leftDepth, rightDepth) 1; // 访问根处理结果 }6.5 递归 vs 迭代在面试中该如何选择这没有绝对答案但可以参考以下策略优先写递归如果面试官没有明确要求先写出简洁正确的递归解法。这能快速展示你对问题本质的理解。主动提及迭代在解释递归解法后可以补充一句“递归解法可能会在树很深时栈溢出我们也可以用迭代栈的方式来模拟这个过程空间复杂度相同但更稳定。”如果面试官要求那就需要流畅地写出迭代解法。通常面试官考察迭代法重点想看的是中序遍历的实现因为它是三种遍历中最需要技巧的。展示知识广度如果时间允许甚至可以提一句“还有一种叫做莫里斯遍历的方法可以在不占用额外栈空间的情况下完成中序遍历不过它会临时修改树的结构”。这能极大提升面试官对你的印象。遍历二叉树远不止记住前中后序的代码那么简单。从递归到迭代从显式栈到莫里斯遍历每一步都加深着我们对程序控制流和数据结构本身的理解。我个人的体会是初学时会觉得迭代法绕但一旦你亲手在纸上模拟几遍栈的变化那种“顿悟”的感觉是非常棒的。它让你从“背诵代码”上升到“理解过程”。下次当你再遇到树的问题时试着先问自己这个问题用哪种遍历顺序最合适是深度优先还是广度优先想清楚了这一点解决方案的框架往往就呼之欲出了。