写二叉树程序的人十个有九个是从中序遍历入门的这话一点不夸张。中序遍历看着简单不就是“左根右”嘛可真要把它写对、写稳能在运行时错误和性能瓶颈里全身而退牵扯出来的东西其实不少。递归、迭代、Morris遍历、线索化、搜索二叉树验证背后全都有它的影子。这篇东西不是教科书复读而是把我在实际开发、面试辅导和排查线上问题过程中跟中序遍历交手的经验整个端出来从三行递归讲到O(1)空间的Morris最后落在“为什么你的二叉树程序总是报运行时错误”这种棘手问题上。不管你是刚学数据结构、正在准备算法面试还是已经被各种诡异崩溃折磨得头大这篇都能给你一点实实在在的参考。1. 中序遍历到底是什么为什么我劝你先把它吃透1.1 三种遍历顺序的本质差异二叉树的遍历就是按某种规则把每个节点恰好访问一次。大家最常听到的三种方式是前序、中序、后序它们的区别只有一个根节点排在什么时候访问。前序遍历根 → 左 → 右中序遍历左 → 根 → 右后序遍历左 → 右 → 根注意这里的“左”和“右”并不是指单个左孩子节点而是指整棵左子树和整棵右子树。拿中序遍历来说它会先完整地走完左子树再回来访问自己最后走完右子树。这句话听起来简单但很多人写代码时会搞混原因就是没有意识到“子树”是递归概念。我习惯用一个类比来理解假设你在一个部门树形结构里点名前序是“领导先报自己再让各团队依次汇报”中序是“先把左边的团队全部点完领导再报自己最后点右边的团队”后序则是“团队全部讲完领导最后才总结”。中序这个顺序天然形成了一种“左边全部处理干净再处理自己”的节奏在搜索二叉树和表达式场景里特别有用。也有不少同学靠口诀记前序“根左右”中序“左根右”后序“左右根”。口诀没错但我更建议理解为什么中序要把访问动作放在递归调用中间。因为中序遍历的定义本来就是递归的先对左子树做中序再访问根节点再对右子树做中序。你只有把“访问根节点”这段代码夹在两个递归调用之间才能保证输出顺序正确。这是定义决定的不是代码风格决定的。1.2 它到底能解决什么问题中序遍历之所以在二叉树算法里存在感极强主要因为它在几个高频场景里都是关键角色。第一搜索二叉树BST中序遍历的结果是一个升序序列。这个特性几乎是BST算法的基础。验证一棵树是不是BST、找出第K小的节点、把BST转成有序双链表、检查两个节点是否被错误交换这些题目十有八九都在利用“中序有序”这条性质。第二表达式树的中序遍历对应我们熟悉的中缀表达式。比如用二叉树表示a b * c根节点是左子树是a右子树是b * c这棵树中序遍历出来就是a b * c。虽然括号位置需要额外处理但这个对应关系让中序遍历在编译器、计算器实现里非常常见。第三线索二叉树靠中序遍历来建立线索。普通二叉树有大量空指针浪费着中序线索化之后空left指向前驱、空right指向后继遍历时不需要递归也不需要栈一路顺着后继走就行。第四前端和后端常见的树形控件、目录树展示如果要按从左到右的自然阅读顺序输出节点中序也是常见选择。比如很多树形选择器在显示时左子树放上面、右子树放下面的“左根右”结构本质就是中序。所以不要觉得中序遍历只是面试题。它就是一棵二叉树按“人脑自然的阅读顺序”输出的方式凡是要把树结构变成线性顺序的场景它都有资格出场。1.3 中序遍历和树的深度、二叉树规模有什么关系这个点经常被忽略。很多人只盯着遍历顺序却忘了递归实现中序遍历时系统调用栈的深度其实取决于树高而不是节点总数。树的高度是什么意思根到最远叶子节点的边数或节点数取决于定义。一颗满二叉树有几百个节点但高度只有个位数而一颗退化成链状的“二叉树”节点数几十个高度就有几十个。中序递归在链状树上会一路深入到最底层调用栈深度也跟树高成正比。换句话说你要写二叉树程序树的深度不是一个无关指标。很多写着写着就“运行时错误”的代码不是逻辑错了而是递归深度把系统栈打爆了。后面我会专门讲这个排查过程但你现在就要有个概念中序遍历的空间复杂度是O(h)h是树高不是O(1)。另外如果你真的需要在遍历过程中知道当前深度传一个depth参数给递归函数就能实现。比如下面的代码能在中序访问时顺便打印当前深度void inorderWithDepth(TreeNode* root, int depth) { if (root nullptr) return; inorderWithDepth(root-left, depth 1); cout 节点 root-val 在深度 depth endl; inorderWithDepth(root-right, depth 1); }这段代码里根节点的depth是0每往下一层就加1。这看起来简单但有时候能帮你快速定位“是不是树太高导致的问题”。2. 递归写法三五行入门但别小看这三五行2.1 递归三要素拆开看递归写中序遍历核心就三件事终止条件、递归调用、什么时候访问当前节点。很多同学写着写着报错通常不是这三件事写不出来而是没有理解它们之间的配合。终止条件通常就是当前节点为空直接return。这是递归的出口也是最容易漏判空指针的地方。递归调用是两次先递归左子树再递归右子树。访问当前节点的那行代码被夹在两次递归调用中间。一旦把访问代码放到递归左子树之前就变成前序遍历放到两个递归之后就变成后序遍历。位置决定顺序顺序决定结果。我见过不少新人的代码长这样void inorder(TreeNode* root) { inorder(root-left); cout root-val endl; inorder(root-right); }一眼看过去没什么但跑起来立刻空指针崩溃。因为没有判断root是否为空root为空时访问 root-left 就是解引用空指针。这几乎是新手第一个运行时错误。你可以在函数入口加上 if (root nullptr) return;也可以把递归调用包在判断里但最干净的方式永远是函数开头判空。还有个更隐蔽的问题有些同学喜欢在写递归时大量使用if (root-left ! nullptr)这种提前判断结果代码越写越长每个分支都要重复访问逻辑。我的建议是先写简单的空指针返回再考虑优化。等代码跑通了再改也不迟。2.2 完整代码和复杂度分析给一个可以直接跑通的中序递归版用C写方便对照。Java、Python思路完全一样把访问逻辑换成对应语法即可。struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; void inorderTraversal(TreeNode* root) { if (root nullptr) return; inorderTraversal(root-left); visit(root-val); inorderTraversal(root-right); }这个版本的访问顺序是严格左根右。假设树是4 / \ 2 6 / \ / \ 1 3 5 7输出就是 1 2 3 4 5 6 7。为什么是升序因为这棵树本身是一个BST中序遍历自然有序。复杂度上每个节点恰好在递归里经过一次时间O(n)。空间上递归调用栈的最高深度等于树的高度平均情况O(log n)最坏情况链状树O(n)。不要看到“递归”就觉得空间是O(1)系统栈是要算进去的。顺便说一句你在很多在线评测系统里提交代码根本不关心日志只要返回值。这时候把访问逻辑替换成往vector里push_back就行。下面这种写法是面试中最常见的void inorder(TreeNode* root, vectorint res) { if (!root) return; inorder(root-left, res); res.push_back(root-val); inorder(root-right, res); }这种用引用传数组的方式在C里很实用递归过程中不断往同一个数组追加结果顺序就是中序。2.3 递归最容易被忽略的边界条件递归本身的逻辑很简单但如果你在评测系统里连续提交多次每次调用一遍有些问题藏得挺深。先说最常见的几个边界情况空树 root nullptr函数应该直接返回空结果。单节点树只输出根节点。只有左子树的链状树输出顺序必须先把整条链走完再访问根再把根右子树空跳过。只有右子树的链状树先访问根再一路走右子树。满二叉树输出结果应该是严格升序如果树是BST。我见过最多的翻车场景是“本地一切正常提交就报错”。这种情况十有八九是测试数据里包含一个超深的链状树递归深度直接把系统栈打爆出现栈溢出。Java的默认栈深度根据JVM参数差异很大C默认栈不大Python直接抛RecursionError。所以“递归写法”只适合树高可控的场景真要面对不可控数据迭代写法是必须掌握的。这一点放到下一节细讲。还有个容易忽略的细节递归里传引用参数时如果同一个函数被多个测试用例反复调用入参数组要记得清空。别问我为什么特地提这个——在真实的工程代码里一个中序遍历函数被十次调用第二次结果变成前一次的拼接这种事一点都不罕见。解决问题的关键是在每次调用入口res.clear()或者在函数内部新建数组再返回。3. 迭代写法手动压栈才算真懂中序3.1 为什么需要迭代版递归实现中序遍历固然短小简洁但它有一个绕不开的软肋调用栈深度受系统限制。当二叉树退化成一长条链树高等于节点数递归深度就可能达到上万层。这时候程序会直接崩溃表现是“运行时错误”你排查半天逻辑看着完全正确就是莫名其妙崩了。迭代写法的本质是把递归隐式的系统栈变成显式的栈容器内存从系统栈转移到堆上可控性大幅提升。道理其实很简单函数递归调用时真正被压栈的是“当前函数还没处理完等子调用返回后要继续干什么”这个状态。我们用栈手动记录这些状态效果完全等价。中序迭代版的核心思路是先把当前节点的整条左链全部压栈直到左孩子为空然后弹栈访问每弹出一个节点就把它当作“当前节点”立即转向右子树再重复“沿左链压到底”的过程。就这么三步反复循环。3.2 样例树逐步走读光说抽象。拿刚才那棵树手动走一遍你就彻底明白了。4 / \ 2 6 / \ / \ 1 3 5 7整个执行过程可以用表格表示栈中元素用右侧作为栈顶步骤当前操作栈内容输出1沿左链压入4, 2, 1cur变为null[4, 2, 1]2弹栈得到1访问cur指向1.right[4, 2]13cur 1.right null继续弹栈得到2访问cur指向2.right[4]1 24cur 3沿左链压入3cur变为null[4, 3]1 25弹栈得到3访问cur指向3.right[4]1 2 36cur为空弹栈得到4访问cur指向4.right[]1 2 3 47cur 6沿左链压入6, 5cur变为null[6, 5]1 2 3 48弹栈得到5访问cur指向5.right[6]1 2 3 4 59cur为空弹栈得到6访问cur指向6.right[]1 2 3 4 610cur 7沿左链压入7cur变为null[7]1 2 3 4 611弹栈得到7访问cur指向7.right[]1 2 3 4 6 7你发现没有整个流程里栈里保存的是“访问完左子树之后还要返回的祖先们”。每次弹栈都是因为当前节点的左子树已经处理完或者本来就没有左子树。所以弹出来就可以放心访问自身再把注意力转向右子树。对应代码vectorint inorderTraversal(TreeNode* root) { vectorint res; stackTreeNode* st; TreeNode* cur root; while (cur ! nullptr || !st.empty()) { while (cur ! nullptr) { st.push(cur); cur cur-left; } cur st.top(); st.pop(); res.push_back(cur-val); cur cur-right; } return res; }这个代码是面试中序迭代的标准答案之一。注意外层循环条件为什么是cur ! nullptr || !st.empty()不是只判断栈非空因为初始化时cur指向root栈是空的如果只判栈就会在根节点还有左子树时直接跳过反过来也不能只判cur非空因为弹栈后cur可能变成null但栈里还有祖先节点要处理。两者是“或”的关系保证处理完所有节点。内层循环while (cur ! nullptr)做的就是“沿左链压到底”跟递归里左子树调用栈被不断压入完全对应。3.3 迭代版容易踩的坑迭代版很多人在第一次写的时候会在三个地方踩坑。第一个坑是循环条件写错。有人写成while (!st.empty())空树时栈为空循环直接跳过结果倒是空列表貌似没问题。但如果是非空树刚开始栈是空的循环体根本进不去结果永远是空。一定要理解初始阶段cur的作用。第二个坑是忘记写cur cur-right;。弹出节点、访问完之后如果你的代码还停留在原有cur不变下一轮会继续尝试把同一个节点压栈死循环。弹栈之后必须把cur移动到右子树哪怕右子树是null也没关系下一次外层循环会判断是否需要继续弹栈。这一步缺失是迭代版最常见的死循环来源。第三个坑出在“访问时机”。有些同学习惯在压栈前就把节点访问了结果输出变成前序。要时刻提醒自己节点第一次遇到时不能访问要等它从左子树绕回来才能访问。这正好是递归中“访问代码放在两个递归调用中间”的迭代对应。另外如果题目要求结果按逆序输出比如右根左那就在中序基础上调整压栈方向先压右链。原理一样但别再从头推一遍。4. 进阶Morris遍历与线索二叉树4.1 Morris遍历O(1)空间的中序遍历递归版空间O(h)迭代版也是O(h)。有没有办法把额外空间压到O(1)有就是Morris遍历。它的核心思想很巧妙利用树中大量空闲的right指针做临时线索让“回退到祖先”不需要栈。思路一句话当前节点cur如果有左子树就找到左子树中最右的那个节点pred这个pred也就是cur在中序遍历里的前驱节点。然后让pred-right临时指向cur相当于在当前节点和它的前驱之间搭一座桥。等遍历完左子树通过这座桥恰好能回到cur这时候再把pred-right恢复成null继续处理cur的右子树。具体流程是如果cur-left为空直接访问cur然后cur cur-right。如果cur-left不为空先找到cur左子树的最右节点pred。如果pred-right为空说明还没搭桥把pred-right设置为cur然后cur cur-left继续深入左子树。如果pred-right等于cur说明桥已经搭好了左子树处理完毕这时恢复pred-right为空访问cur然后cur cur-right。代码长这样void inorderMorris(TreeNode* root) { TreeNode* cur root; while (cur ! nullptr) { if (cur-left nullptr) { visit(cur); cur cur-right; } else { TreeNode* pred cur-left; while (pred-right ! nullptr pred-right ! cur) { pred pred-right; } if (pred-right nullptr) { pred-right cur; cur cur-left; } else { pred-right nullptr; visit(cur); cur cur-right; } } } }几个实测要注意的细节找前驱的while循环条件必须写成pred-right ! nullptr pred-right ! cur为什么要判断pred-right ! cur因为第二次遍历到这个节点时前驱的right已经被设置成cur了如果不去判断就会死循环。另外当发现pred-right等于cur时说明桥已经建好访问完cur之后要赶紧把pred-right恢复成null保持树的原始结构。如果不恢复原树就被永久改坏了后续任何依赖正常结构的操作都可能出问题。这也是很多人在工程里不敢用Morris的原因——它确实会临时修改树而且线程不安全。时间复杂度看起来有个找前驱的内层循环但每个节点作为前驱被找的次数是常数次整体依然是O(n)。空间是O(1)这在高性能场景或者处理超大二叉树时很香。4.2 线索二叉树把空指针变成前驱/后继Morris遍历是“遍历时建临时线索用完就拆”线索二叉树则是“提前把线索建成永久结构”。普通二叉树n个节点有n1个空指针放着也是浪费。中序线索化就是让空的left指向中序遍历下的前驱节点让空的right指向中序遍历下的后继节点。因为要区分“这个指针是真实的左孩子”还是“中序前驱线索”通常给每个节点加两个标志ltag和rtag。0表示指针指向孩子1表示指针指向线索。中序线索化的过程其实就是在中序遍历过程中记录上一个访问的节点prev。当访问到当前节点cur时如果cur-left为空就让cur-left指向prev并置ltag1如果prev-right为空就让prev-right指向cur并置rtag1。这里的prev就是cur在中序序列里的前驱这个对应关系不能搞反。用C写一个中序线索化struct ThreadNode { int val; ThreadNode *left, *right; int ltag, rtag; ThreadNode(int x) : val(x), left(nullptr), right(nullptr), ltag(0), rtag(0) {} }; void inThread(ThreadNode* cur, ThreadNode* prev) { if (cur nullptr) return; inThread(cur-left, prev); if (cur-left nullptr) { cur-left prev; cur-ltag 1; } if (prev ! nullptr prev-right nullptr) { prev-right cur; prev-rtag 1; } prev cur; inThread(cur-right, prev); }注意prev必须用引用传因为在递归过程中prev要跟着访问顺序不断更新一直指向中序序列里的“上一个节点”。如果你用值传递prev在每次递归返回后没法保留状态线索化必然出错。中序线索化之后找任意节点的中序后继就有规则了如果rtag是1right指的就是后继如果rtag是0说明有右子树那后继就是右子树中“最左的节点”。这个规则让遍历不需要栈和递归就能完成属于“空间换时间、又用时间省空间”的经典玩法。理解了Morris和线索化你对中序遍历的掌控力就完全不一样了。5. 中序遍历遇上搜索二叉树一对王炸组合5.1 中序让BST变成天然有序数组搜索二叉树BST的定义很严格左子树所有节点值小于根根小于右子树所有节点值且要求左右子树也各自满足这个规则。因为中序遍历的顺序是左根右而BST里“左都小于根、右都大于根”所以中序遍历出来的序列必然是升序的。这条性质是中序相关题目最核心的武器。这个结论反过来也成立如果一颗二叉树的中序遍历结果严格递增那它大概率就是BST前提是节点值不重复且按常见定义没有重复值。这给了我们一个很实用的直觉——处理BST时把“中序”和“有序”当成同义词也问题不大。工程里BST经常被用来做有序集合或有序映射。比如红黑树、AVL树底层就是BST的变体对它们做中序输出得到的就是一个排序好的数组。所以树结构在某些场景下比数组更灵活插入删除O(log n)需要有序结果时中序遍历直接导出。5.2 用中序做BST验证、找第K小、恢复异常节点既然BST的中序是严格递增的我们就可以做不少有意思的题目。第一个是验证BST。不用递归比较每个节点和整棵树的最大最小值区间直接中序遍历检查每个节点值是否严格大于前一个值。代码可以复用迭代版加一个prev记录bool isValidBST(TreeNode* root) { stackTreeNode* st; TreeNode* cur root; long long prev LLONG_MIN; while (cur ! nullptr || !st.empty()) { while (cur ! nullptr) { st.push(cur); cur cur-left; } cur st.top(); st.pop(); if (cur-val prev) return false; prev cur-val; cur cur-right; } return true; }注意用long long并把prev初始化为LLONG_MIN可以规避节点值等于INT_MIN的边界用例。这个细节在LeetCode 98这类题目上很关键。第二个是找第K小的节点。BST中序就是升序中序遍历时数到第K个就是答案。这个做法的复杂度是O(n)如果树被改造成带子树大小计数的平衡树可以优化到O(log n)但面试里先写O(n)版本也完全合格。第三个是恢复被交换的两个节点。题目通常叫“恢复二叉搜索树”就是BST里两个节点值被意外交换了让你在不改变树结构的前提下改回正确的值。这题最优雅的解法也是中序遍历正常BST中序遍历是严格递增的交换两个节点后序列里必然有一到两处逆序。找到这两个位置交换它们的值就能修复。原理简单但用中序遍历定位异常位置时要把两个异常节点的判断逻辑写清楚这是个很好的练手题。5.3 中序前序重建二叉树为什么中序能当“分界线”另一道经典题是用前序和中序遍历结果重建二叉树。前序序列的第一个节点一定是根节点但光看前序你分不清左右子树的边界。中序序列就补上了这个信息根节点在中序里的位置左边就是整个左子树的中序序列右边就是整个右子树的中序序列。举例来说前序是[4, 2, 1, 3, 6, 5, 7]根节点是4。中序是[1, 2, 3, 4, 5, 6, 7]4把中序分成左半[1, 2, 3]和右半[5, 6, 7]。再从前序里切出左子树的前序[2, 1, 3]和右子树的前序[6, 5, 7]两边递归建树即可。这就是为什么很多资料说中序在重建过程中是“分界线”。没有中序前序和后序组合不能唯一确定一棵二叉树这个点当年面试时也经常被问到。这个思路还可以延伸到反序列化。二叉树序列化时如果你把前序和中序都保存下来就能完整恢复原树。工程里的树形结构传输、缓存序列化经常能看到这种组合策略。6. 运行时错误排查为什么你的二叉树程序总是崩6.1 常见运行时错误速查表说句扎心的话很多同学报“运行时错误”的时候第一反应是自己逻辑错了翻来覆去看中序遍历顺序都对但程序就是崩溃。根据这些年的经验我把最常见的几个错误汇总成一张表对照着查效率会高很多错误表现可能原因排查思路解决建议空指针异常 / Segmentation Fault对NULL节点直接访问left或right打印递归入口处的root指针看崩溃栈递归/循环开头判空统一 nullptr栈溢出 / RecursionError树高太大递归深度超限检查测试数据里有没有链状树改迭代版或者调大系统栈内存耗尽 / bad_alloc每个用例new节点不释放测试数据拷贝过多跑内存检测工具智能指针管理用例结束统一释放程序不退出 / 死循环迭代版弹栈后没写curcur-rightMorris前驱成环在循环里加计数器打印检查每次指针移动输出结果错了递归顺序或访问位置写错用三节点小树手推先验最小用例再验大用例多次调用结果混在一起全局变量prev或结果数组没重置同一个函数连续跑两次对比每次调用前清空状态这里要特别强调运行时错误并不等于逻辑错误。如果你的算法在本地几个样例全过一到在线测评就崩优先怀疑“输入数据规模”和“树形结构”超出你的预期。链状树这个测试用例几乎能精准命中递归写法的时间炸弹。6.2 排查的三个小习惯第一个习惯是准备好测试矩阵。别只测题目给的样例。我常用的二叉树测试矩阵包括空树、单节点、满二叉树、只有左链、只有右链、随机大树、超高链状树。这七种跑一遍递归溢出的问题基本就是瞬间暴露。第二个习惯是在递归函数入口打印状态。调试中序遍历时我经常在函数最开头加一行日志输出当前节点指针和值再在离开函数之前打印一次。用这种“进出成对”的日志能很快看清递归调用的推进顺序也能发现谁在递归里被反复传入NULL或者重复处理同一个节点。第三个习惯是写一个随机二叉树生成器。我自己维护了一个小工具传入节点数和最大树高随机生成两种树一种是尽量平衡的随机树一种是故意退化成链状的极端树。中序遍历代码写完先拿随机树跑再拿链状树跑很多隐藏问题当场现形。这些习惯看起来笨拙但比起对着代码干瞪眼要高效得多。6.3 我踩过的几个真实坑第一个坑是全局变量prev没重置。当时写线索化和中序验证BST的代码把prev定义成成员变量第一次调用完全正确第二次调用因为prev还保留着上一次遍历的末尾节点直接导致判断失败。从那以后我所有需要记录“前一个节点”的场景一律在函数内部用局部变量或者明确在函数入口重置。第二个坑是Morris遍历恢复不干净。有一次我在一个功能里用Morris遍历做统计函数执行完没把最后几个前驱节点的right指针恢复成null结果同一个树对象后面再做层序遍历时莫名出现了死循环。这个bug查了半天最后才发现是Morris留下的“桥”没拆。所以用Morris之后最好对同一个树再做一次中序遍历验证结构没变。第三个坑是线索化忘记置ltag和rtag。线索化代码一看就会一写就错。原因就是只在设置指针时修改了指向忘了把标志位置为1。结果遍历时遇到一个“线索”当成真孩子继续递归下去直接炸栈。这个问题的排查难度挺高因为错误不在顺序而在节点状态的完整性。现在我的习惯是涉及线索二叉树必须先确保每个节点初始化时ltag和rtag都置0线索化时再逐个改。说到底二叉树程序崩溃绝大多数原因就两类一类是空指针一类是递归深度。中序本身不复杂复杂的是你在各种极端输入下还能保持冷静逐个排查。我个人这些年越来越觉得中序遍历就像一把尺子能度量你对递归、栈、有序性和树结构的理解程度。真正把递归版、迭代版、Morris版都亲手写一遍再把BST验证、线索化这些应用场景串起来你会发现它们本质上都是同一个“左根右”逻辑在不同资源约束下的变形。最后一点小建议写这类题目时永远从三节点的小树开始验证再逐步放大出问题先问自己“树高多少、空指针能不能访问、状态有没有重置”。这三句话能帮你躲过大部分运行时错误。
中序遍历二叉树全解读：从递归到Morris，避开运行时错误
写二叉树程序的人十个有九个是从中序遍历入门的这话一点不夸张。中序遍历看着简单不就是“左根右”嘛可真要把它写对、写稳能在运行时错误和性能瓶颈里全身而退牵扯出来的东西其实不少。递归、迭代、Morris遍历、线索化、搜索二叉树验证背后全都有它的影子。这篇东西不是教科书复读而是把我在实际开发、面试辅导和排查线上问题过程中跟中序遍历交手的经验整个端出来从三行递归讲到O(1)空间的Morris最后落在“为什么你的二叉树程序总是报运行时错误”这种棘手问题上。不管你是刚学数据结构、正在准备算法面试还是已经被各种诡异崩溃折磨得头大这篇都能给你一点实实在在的参考。1. 中序遍历到底是什么为什么我劝你先把它吃透1.1 三种遍历顺序的本质差异二叉树的遍历就是按某种规则把每个节点恰好访问一次。大家最常听到的三种方式是前序、中序、后序它们的区别只有一个根节点排在什么时候访问。前序遍历根 → 左 → 右中序遍历左 → 根 → 右后序遍历左 → 右 → 根注意这里的“左”和“右”并不是指单个左孩子节点而是指整棵左子树和整棵右子树。拿中序遍历来说它会先完整地走完左子树再回来访问自己最后走完右子树。这句话听起来简单但很多人写代码时会搞混原因就是没有意识到“子树”是递归概念。我习惯用一个类比来理解假设你在一个部门树形结构里点名前序是“领导先报自己再让各团队依次汇报”中序是“先把左边的团队全部点完领导再报自己最后点右边的团队”后序则是“团队全部讲完领导最后才总结”。中序这个顺序天然形成了一种“左边全部处理干净再处理自己”的节奏在搜索二叉树和表达式场景里特别有用。也有不少同学靠口诀记前序“根左右”中序“左根右”后序“左右根”。口诀没错但我更建议理解为什么中序要把访问动作放在递归调用中间。因为中序遍历的定义本来就是递归的先对左子树做中序再访问根节点再对右子树做中序。你只有把“访问根节点”这段代码夹在两个递归调用之间才能保证输出顺序正确。这是定义决定的不是代码风格决定的。1.2 它到底能解决什么问题中序遍历之所以在二叉树算法里存在感极强主要因为它在几个高频场景里都是关键角色。第一搜索二叉树BST中序遍历的结果是一个升序序列。这个特性几乎是BST算法的基础。验证一棵树是不是BST、找出第K小的节点、把BST转成有序双链表、检查两个节点是否被错误交换这些题目十有八九都在利用“中序有序”这条性质。第二表达式树的中序遍历对应我们熟悉的中缀表达式。比如用二叉树表示a b * c根节点是左子树是a右子树是b * c这棵树中序遍历出来就是a b * c。虽然括号位置需要额外处理但这个对应关系让中序遍历在编译器、计算器实现里非常常见。第三线索二叉树靠中序遍历来建立线索。普通二叉树有大量空指针浪费着中序线索化之后空left指向前驱、空right指向后继遍历时不需要递归也不需要栈一路顺着后继走就行。第四前端和后端常见的树形控件、目录树展示如果要按从左到右的自然阅读顺序输出节点中序也是常见选择。比如很多树形选择器在显示时左子树放上面、右子树放下面的“左根右”结构本质就是中序。所以不要觉得中序遍历只是面试题。它就是一棵二叉树按“人脑自然的阅读顺序”输出的方式凡是要把树结构变成线性顺序的场景它都有资格出场。1.3 中序遍历和树的深度、二叉树规模有什么关系这个点经常被忽略。很多人只盯着遍历顺序却忘了递归实现中序遍历时系统调用栈的深度其实取决于树高而不是节点总数。树的高度是什么意思根到最远叶子节点的边数或节点数取决于定义。一颗满二叉树有几百个节点但高度只有个位数而一颗退化成链状的“二叉树”节点数几十个高度就有几十个。中序递归在链状树上会一路深入到最底层调用栈深度也跟树高成正比。换句话说你要写二叉树程序树的深度不是一个无关指标。很多写着写着就“运行时错误”的代码不是逻辑错了而是递归深度把系统栈打爆了。后面我会专门讲这个排查过程但你现在就要有个概念中序遍历的空间复杂度是O(h)h是树高不是O(1)。另外如果你真的需要在遍历过程中知道当前深度传一个depth参数给递归函数就能实现。比如下面的代码能在中序访问时顺便打印当前深度void inorderWithDepth(TreeNode* root, int depth) { if (root nullptr) return; inorderWithDepth(root-left, depth 1); cout 节点 root-val 在深度 depth endl; inorderWithDepth(root-right, depth 1); }这段代码里根节点的depth是0每往下一层就加1。这看起来简单但有时候能帮你快速定位“是不是树太高导致的问题”。2. 递归写法三五行入门但别小看这三五行2.1 递归三要素拆开看递归写中序遍历核心就三件事终止条件、递归调用、什么时候访问当前节点。很多同学写着写着报错通常不是这三件事写不出来而是没有理解它们之间的配合。终止条件通常就是当前节点为空直接return。这是递归的出口也是最容易漏判空指针的地方。递归调用是两次先递归左子树再递归右子树。访问当前节点的那行代码被夹在两次递归调用中间。一旦把访问代码放到递归左子树之前就变成前序遍历放到两个递归之后就变成后序遍历。位置决定顺序顺序决定结果。我见过不少新人的代码长这样void inorder(TreeNode* root) { inorder(root-left); cout root-val endl; inorder(root-right); }一眼看过去没什么但跑起来立刻空指针崩溃。因为没有判断root是否为空root为空时访问 root-left 就是解引用空指针。这几乎是新手第一个运行时错误。你可以在函数入口加上 if (root nullptr) return;也可以把递归调用包在判断里但最干净的方式永远是函数开头判空。还有个更隐蔽的问题有些同学喜欢在写递归时大量使用if (root-left ! nullptr)这种提前判断结果代码越写越长每个分支都要重复访问逻辑。我的建议是先写简单的空指针返回再考虑优化。等代码跑通了再改也不迟。2.2 完整代码和复杂度分析给一个可以直接跑通的中序递归版用C写方便对照。Java、Python思路完全一样把访问逻辑换成对应语法即可。struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; void inorderTraversal(TreeNode* root) { if (root nullptr) return; inorderTraversal(root-left); visit(root-val); inorderTraversal(root-right); }这个版本的访问顺序是严格左根右。假设树是4 / \ 2 6 / \ / \ 1 3 5 7输出就是 1 2 3 4 5 6 7。为什么是升序因为这棵树本身是一个BST中序遍历自然有序。复杂度上每个节点恰好在递归里经过一次时间O(n)。空间上递归调用栈的最高深度等于树的高度平均情况O(log n)最坏情况链状树O(n)。不要看到“递归”就觉得空间是O(1)系统栈是要算进去的。顺便说一句你在很多在线评测系统里提交代码根本不关心日志只要返回值。这时候把访问逻辑替换成往vector里push_back就行。下面这种写法是面试中最常见的void inorder(TreeNode* root, vectorint res) { if (!root) return; inorder(root-left, res); res.push_back(root-val); inorder(root-right, res); }这种用引用传数组的方式在C里很实用递归过程中不断往同一个数组追加结果顺序就是中序。2.3 递归最容易被忽略的边界条件递归本身的逻辑很简单但如果你在评测系统里连续提交多次每次调用一遍有些问题藏得挺深。先说最常见的几个边界情况空树 root nullptr函数应该直接返回空结果。单节点树只输出根节点。只有左子树的链状树输出顺序必须先把整条链走完再访问根再把根右子树空跳过。只有右子树的链状树先访问根再一路走右子树。满二叉树输出结果应该是严格升序如果树是BST。我见过最多的翻车场景是“本地一切正常提交就报错”。这种情况十有八九是测试数据里包含一个超深的链状树递归深度直接把系统栈打爆出现栈溢出。Java的默认栈深度根据JVM参数差异很大C默认栈不大Python直接抛RecursionError。所以“递归写法”只适合树高可控的场景真要面对不可控数据迭代写法是必须掌握的。这一点放到下一节细讲。还有个容易忽略的细节递归里传引用参数时如果同一个函数被多个测试用例反复调用入参数组要记得清空。别问我为什么特地提这个——在真实的工程代码里一个中序遍历函数被十次调用第二次结果变成前一次的拼接这种事一点都不罕见。解决问题的关键是在每次调用入口res.clear()或者在函数内部新建数组再返回。3. 迭代写法手动压栈才算真懂中序3.1 为什么需要迭代版递归实现中序遍历固然短小简洁但它有一个绕不开的软肋调用栈深度受系统限制。当二叉树退化成一长条链树高等于节点数递归深度就可能达到上万层。这时候程序会直接崩溃表现是“运行时错误”你排查半天逻辑看着完全正确就是莫名其妙崩了。迭代写法的本质是把递归隐式的系统栈变成显式的栈容器内存从系统栈转移到堆上可控性大幅提升。道理其实很简单函数递归调用时真正被压栈的是“当前函数还没处理完等子调用返回后要继续干什么”这个状态。我们用栈手动记录这些状态效果完全等价。中序迭代版的核心思路是先把当前节点的整条左链全部压栈直到左孩子为空然后弹栈访问每弹出一个节点就把它当作“当前节点”立即转向右子树再重复“沿左链压到底”的过程。就这么三步反复循环。3.2 样例树逐步走读光说抽象。拿刚才那棵树手动走一遍你就彻底明白了。4 / \ 2 6 / \ / \ 1 3 5 7整个执行过程可以用表格表示栈中元素用右侧作为栈顶步骤当前操作栈内容输出1沿左链压入4, 2, 1cur变为null[4, 2, 1]2弹栈得到1访问cur指向1.right[4, 2]13cur 1.right null继续弹栈得到2访问cur指向2.right[4]1 24cur 3沿左链压入3cur变为null[4, 3]1 25弹栈得到3访问cur指向3.right[4]1 2 36cur为空弹栈得到4访问cur指向4.right[]1 2 3 47cur 6沿左链压入6, 5cur变为null[6, 5]1 2 3 48弹栈得到5访问cur指向5.right[6]1 2 3 4 59cur为空弹栈得到6访问cur指向6.right[]1 2 3 4 610cur 7沿左链压入7cur变为null[7]1 2 3 4 611弹栈得到7访问cur指向7.right[]1 2 3 4 6 7你发现没有整个流程里栈里保存的是“访问完左子树之后还要返回的祖先们”。每次弹栈都是因为当前节点的左子树已经处理完或者本来就没有左子树。所以弹出来就可以放心访问自身再把注意力转向右子树。对应代码vectorint inorderTraversal(TreeNode* root) { vectorint res; stackTreeNode* st; TreeNode* cur root; while (cur ! nullptr || !st.empty()) { while (cur ! nullptr) { st.push(cur); cur cur-left; } cur st.top(); st.pop(); res.push_back(cur-val); cur cur-right; } return res; }这个代码是面试中序迭代的标准答案之一。注意外层循环条件为什么是cur ! nullptr || !st.empty()不是只判断栈非空因为初始化时cur指向root栈是空的如果只判栈就会在根节点还有左子树时直接跳过反过来也不能只判cur非空因为弹栈后cur可能变成null但栈里还有祖先节点要处理。两者是“或”的关系保证处理完所有节点。内层循环while (cur ! nullptr)做的就是“沿左链压到底”跟递归里左子树调用栈被不断压入完全对应。3.3 迭代版容易踩的坑迭代版很多人在第一次写的时候会在三个地方踩坑。第一个坑是循环条件写错。有人写成while (!st.empty())空树时栈为空循环直接跳过结果倒是空列表貌似没问题。但如果是非空树刚开始栈是空的循环体根本进不去结果永远是空。一定要理解初始阶段cur的作用。第二个坑是忘记写cur cur-right;。弹出节点、访问完之后如果你的代码还停留在原有cur不变下一轮会继续尝试把同一个节点压栈死循环。弹栈之后必须把cur移动到右子树哪怕右子树是null也没关系下一次外层循环会判断是否需要继续弹栈。这一步缺失是迭代版最常见的死循环来源。第三个坑出在“访问时机”。有些同学习惯在压栈前就把节点访问了结果输出变成前序。要时刻提醒自己节点第一次遇到时不能访问要等它从左子树绕回来才能访问。这正好是递归中“访问代码放在两个递归调用中间”的迭代对应。另外如果题目要求结果按逆序输出比如右根左那就在中序基础上调整压栈方向先压右链。原理一样但别再从头推一遍。4. 进阶Morris遍历与线索二叉树4.1 Morris遍历O(1)空间的中序遍历递归版空间O(h)迭代版也是O(h)。有没有办法把额外空间压到O(1)有就是Morris遍历。它的核心思想很巧妙利用树中大量空闲的right指针做临时线索让“回退到祖先”不需要栈。思路一句话当前节点cur如果有左子树就找到左子树中最右的那个节点pred这个pred也就是cur在中序遍历里的前驱节点。然后让pred-right临时指向cur相当于在当前节点和它的前驱之间搭一座桥。等遍历完左子树通过这座桥恰好能回到cur这时候再把pred-right恢复成null继续处理cur的右子树。具体流程是如果cur-left为空直接访问cur然后cur cur-right。如果cur-left不为空先找到cur左子树的最右节点pred。如果pred-right为空说明还没搭桥把pred-right设置为cur然后cur cur-left继续深入左子树。如果pred-right等于cur说明桥已经搭好了左子树处理完毕这时恢复pred-right为空访问cur然后cur cur-right。代码长这样void inorderMorris(TreeNode* root) { TreeNode* cur root; while (cur ! nullptr) { if (cur-left nullptr) { visit(cur); cur cur-right; } else { TreeNode* pred cur-left; while (pred-right ! nullptr pred-right ! cur) { pred pred-right; } if (pred-right nullptr) { pred-right cur; cur cur-left; } else { pred-right nullptr; visit(cur); cur cur-right; } } } }几个实测要注意的细节找前驱的while循环条件必须写成pred-right ! nullptr pred-right ! cur为什么要判断pred-right ! cur因为第二次遍历到这个节点时前驱的right已经被设置成cur了如果不去判断就会死循环。另外当发现pred-right等于cur时说明桥已经建好访问完cur之后要赶紧把pred-right恢复成null保持树的原始结构。如果不恢复原树就被永久改坏了后续任何依赖正常结构的操作都可能出问题。这也是很多人在工程里不敢用Morris的原因——它确实会临时修改树而且线程不安全。时间复杂度看起来有个找前驱的内层循环但每个节点作为前驱被找的次数是常数次整体依然是O(n)。空间是O(1)这在高性能场景或者处理超大二叉树时很香。4.2 线索二叉树把空指针变成前驱/后继Morris遍历是“遍历时建临时线索用完就拆”线索二叉树则是“提前把线索建成永久结构”。普通二叉树n个节点有n1个空指针放着也是浪费。中序线索化就是让空的left指向中序遍历下的前驱节点让空的right指向中序遍历下的后继节点。因为要区分“这个指针是真实的左孩子”还是“中序前驱线索”通常给每个节点加两个标志ltag和rtag。0表示指针指向孩子1表示指针指向线索。中序线索化的过程其实就是在中序遍历过程中记录上一个访问的节点prev。当访问到当前节点cur时如果cur-left为空就让cur-left指向prev并置ltag1如果prev-right为空就让prev-right指向cur并置rtag1。这里的prev就是cur在中序序列里的前驱这个对应关系不能搞反。用C写一个中序线索化struct ThreadNode { int val; ThreadNode *left, *right; int ltag, rtag; ThreadNode(int x) : val(x), left(nullptr), right(nullptr), ltag(0), rtag(0) {} }; void inThread(ThreadNode* cur, ThreadNode* prev) { if (cur nullptr) return; inThread(cur-left, prev); if (cur-left nullptr) { cur-left prev; cur-ltag 1; } if (prev ! nullptr prev-right nullptr) { prev-right cur; prev-rtag 1; } prev cur; inThread(cur-right, prev); }注意prev必须用引用传因为在递归过程中prev要跟着访问顺序不断更新一直指向中序序列里的“上一个节点”。如果你用值传递prev在每次递归返回后没法保留状态线索化必然出错。中序线索化之后找任意节点的中序后继就有规则了如果rtag是1right指的就是后继如果rtag是0说明有右子树那后继就是右子树中“最左的节点”。这个规则让遍历不需要栈和递归就能完成属于“空间换时间、又用时间省空间”的经典玩法。理解了Morris和线索化你对中序遍历的掌控力就完全不一样了。5. 中序遍历遇上搜索二叉树一对王炸组合5.1 中序让BST变成天然有序数组搜索二叉树BST的定义很严格左子树所有节点值小于根根小于右子树所有节点值且要求左右子树也各自满足这个规则。因为中序遍历的顺序是左根右而BST里“左都小于根、右都大于根”所以中序遍历出来的序列必然是升序的。这条性质是中序相关题目最核心的武器。这个结论反过来也成立如果一颗二叉树的中序遍历结果严格递增那它大概率就是BST前提是节点值不重复且按常见定义没有重复值。这给了我们一个很实用的直觉——处理BST时把“中序”和“有序”当成同义词也问题不大。工程里BST经常被用来做有序集合或有序映射。比如红黑树、AVL树底层就是BST的变体对它们做中序输出得到的就是一个排序好的数组。所以树结构在某些场景下比数组更灵活插入删除O(log n)需要有序结果时中序遍历直接导出。5.2 用中序做BST验证、找第K小、恢复异常节点既然BST的中序是严格递增的我们就可以做不少有意思的题目。第一个是验证BST。不用递归比较每个节点和整棵树的最大最小值区间直接中序遍历检查每个节点值是否严格大于前一个值。代码可以复用迭代版加一个prev记录bool isValidBST(TreeNode* root) { stackTreeNode* st; TreeNode* cur root; long long prev LLONG_MIN; while (cur ! nullptr || !st.empty()) { while (cur ! nullptr) { st.push(cur); cur cur-left; } cur st.top(); st.pop(); if (cur-val prev) return false; prev cur-val; cur cur-right; } return true; }注意用long long并把prev初始化为LLONG_MIN可以规避节点值等于INT_MIN的边界用例。这个细节在LeetCode 98这类题目上很关键。第二个是找第K小的节点。BST中序就是升序中序遍历时数到第K个就是答案。这个做法的复杂度是O(n)如果树被改造成带子树大小计数的平衡树可以优化到O(log n)但面试里先写O(n)版本也完全合格。第三个是恢复被交换的两个节点。题目通常叫“恢复二叉搜索树”就是BST里两个节点值被意外交换了让你在不改变树结构的前提下改回正确的值。这题最优雅的解法也是中序遍历正常BST中序遍历是严格递增的交换两个节点后序列里必然有一到两处逆序。找到这两个位置交换它们的值就能修复。原理简单但用中序遍历定位异常位置时要把两个异常节点的判断逻辑写清楚这是个很好的练手题。5.3 中序前序重建二叉树为什么中序能当“分界线”另一道经典题是用前序和中序遍历结果重建二叉树。前序序列的第一个节点一定是根节点但光看前序你分不清左右子树的边界。中序序列就补上了这个信息根节点在中序里的位置左边就是整个左子树的中序序列右边就是整个右子树的中序序列。举例来说前序是[4, 2, 1, 3, 6, 5, 7]根节点是4。中序是[1, 2, 3, 4, 5, 6, 7]4把中序分成左半[1, 2, 3]和右半[5, 6, 7]。再从前序里切出左子树的前序[2, 1, 3]和右子树的前序[6, 5, 7]两边递归建树即可。这就是为什么很多资料说中序在重建过程中是“分界线”。没有中序前序和后序组合不能唯一确定一棵二叉树这个点当年面试时也经常被问到。这个思路还可以延伸到反序列化。二叉树序列化时如果你把前序和中序都保存下来就能完整恢复原树。工程里的树形结构传输、缓存序列化经常能看到这种组合策略。6. 运行时错误排查为什么你的二叉树程序总是崩6.1 常见运行时错误速查表说句扎心的话很多同学报“运行时错误”的时候第一反应是自己逻辑错了翻来覆去看中序遍历顺序都对但程序就是崩溃。根据这些年的经验我把最常见的几个错误汇总成一张表对照着查效率会高很多错误表现可能原因排查思路解决建议空指针异常 / Segmentation Fault对NULL节点直接访问left或right打印递归入口处的root指针看崩溃栈递归/循环开头判空统一 nullptr栈溢出 / RecursionError树高太大递归深度超限检查测试数据里有没有链状树改迭代版或者调大系统栈内存耗尽 / bad_alloc每个用例new节点不释放测试数据拷贝过多跑内存检测工具智能指针管理用例结束统一释放程序不退出 / 死循环迭代版弹栈后没写curcur-rightMorris前驱成环在循环里加计数器打印检查每次指针移动输出结果错了递归顺序或访问位置写错用三节点小树手推先验最小用例再验大用例多次调用结果混在一起全局变量prev或结果数组没重置同一个函数连续跑两次对比每次调用前清空状态这里要特别强调运行时错误并不等于逻辑错误。如果你的算法在本地几个样例全过一到在线测评就崩优先怀疑“输入数据规模”和“树形结构”超出你的预期。链状树这个测试用例几乎能精准命中递归写法的时间炸弹。6.2 排查的三个小习惯第一个习惯是准备好测试矩阵。别只测题目给的样例。我常用的二叉树测试矩阵包括空树、单节点、满二叉树、只有左链、只有右链、随机大树、超高链状树。这七种跑一遍递归溢出的问题基本就是瞬间暴露。第二个习惯是在递归函数入口打印状态。调试中序遍历时我经常在函数最开头加一行日志输出当前节点指针和值再在离开函数之前打印一次。用这种“进出成对”的日志能很快看清递归调用的推进顺序也能发现谁在递归里被反复传入NULL或者重复处理同一个节点。第三个习惯是写一个随机二叉树生成器。我自己维护了一个小工具传入节点数和最大树高随机生成两种树一种是尽量平衡的随机树一种是故意退化成链状的极端树。中序遍历代码写完先拿随机树跑再拿链状树跑很多隐藏问题当场现形。这些习惯看起来笨拙但比起对着代码干瞪眼要高效得多。6.3 我踩过的几个真实坑第一个坑是全局变量prev没重置。当时写线索化和中序验证BST的代码把prev定义成成员变量第一次调用完全正确第二次调用因为prev还保留着上一次遍历的末尾节点直接导致判断失败。从那以后我所有需要记录“前一个节点”的场景一律在函数内部用局部变量或者明确在函数入口重置。第二个坑是Morris遍历恢复不干净。有一次我在一个功能里用Morris遍历做统计函数执行完没把最后几个前驱节点的right指针恢复成null结果同一个树对象后面再做层序遍历时莫名出现了死循环。这个bug查了半天最后才发现是Morris留下的“桥”没拆。所以用Morris之后最好对同一个树再做一次中序遍历验证结构没变。第三个坑是线索化忘记置ltag和rtag。线索化代码一看就会一写就错。原因就是只在设置指针时修改了指向忘了把标志位置为1。结果遍历时遇到一个“线索”当成真孩子继续递归下去直接炸栈。这个问题的排查难度挺高因为错误不在顺序而在节点状态的完整性。现在我的习惯是涉及线索二叉树必须先确保每个节点初始化时ltag和rtag都置0线索化时再逐个改。说到底二叉树程序崩溃绝大多数原因就两类一类是空指针一类是递归深度。中序本身不复杂复杂的是你在各种极端输入下还能保持冷静逐个排查。我个人这些年越来越觉得中序遍历就像一把尺子能度量你对递归、栈、有序性和树结构的理解程度。真正把递归版、迭代版、Morris版都亲手写一遍再把BST验证、线索化这些应用场景串起来你会发现它们本质上都是同一个“左根右”逻辑在不同资源约束下的变形。最后一点小建议写这类题目时永远从三节点的小树开始验证再逐步放大出问题先问自己“树高多少、空指针能不能访问、状态有没有重置”。这三句话能帮你躲过大部分运行时错误。
