刷 LeetCode 的时候很多人第一道二叉树题做的都是中序遍历。这题表面上看着特别基础递归写法十来行就能完事可一旦较真起来会发现里面藏着不少东西。中序遍历是二叉树三种深度优先遍历里唯一能天然保持“左子树全部处理完再来根节点最后右子树”这种严格顺序的遍历方式而正是这个顺序让它在二叉搜索树的处理上拥有不可替代的地位。本文用 C 把递归、迭代和 Morris 线索化三种解法全部过一遍逐个分析原理、时间空间复杂度再把 OJ 上容易踩的坑一个个点出来。不管你是刚接触二叉树的新手还是准备面试需要系统梳理的老手这篇文章都能给出可以直接参考的实现方案。1. 题目拆解中序遍历到底在遍历什么1.1 题目原题与基本约定先看题面给一棵二叉树的根节点 root返回它的中序遍历结果。OJ 上要求返回一个vectorint元素顺序就是中序遍历访问节点的顺序。这里的二叉树节点定义是标准的三件套struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} };这个定义在二叉树相关题目里几乎是统一模板三个构造函数分别对应默认构造、只给值和完整构造。实际刷题时你通常不需要自己构造 TreeNode因为平台已经做好了建树和传参但理解它的结构很重要val 是节点值left 和 right 是指向下一个节点的指针叶子节点的左右指针都是 nullptr。1.2 前序、中序、后序的遍历顺序二叉树的深度优先遍历有三种顺序区别只在于“根节点什么时候被访问”。前序遍历是根左右中序遍历是左根右后序遍历是左右根。很多初学者容易记混我习惯用“根在哪个位置”来记忆根在前就是前序根在中间就是中序根在最后就是后序。三个名字描述的是根节点在整棵子树的访问时机并不是说左子树和右子树的相对顺序会变。中序遍历的执行过程可以描述为递归遍历左子树访问当前根节点递归遍历右子树。这个“左根右”的顺序在一个二叉搜索树上会呈现一个非常有规律的结果。举个例子一棵搜索树4 / \ 2 6 / \ / \ 1 3 5 7中序遍历输出是 1 2 3 4 5 6 7正好是排序后的序列。这不是巧合而是二叉搜索树的中序遍历天然有序这个性质在后面解决“验证二叉搜索树”“寻找第 k 小元素”等题目时是核心抓手。1.3 为什么单独拿中序遍历讲前序和后序更多用于树的构建、序列化、表达式求值等场景而中序因为“天然有序”这个特点在面试和算法题里被用得最多。这道题作为最基础的一道本质上是给下面一系列题目打底验证二叉搜索树、二叉树中第 k 小的元素、二叉搜索树的最小绝对差、恢复二叉搜索树等等全都是在中序遍历结果上做文章。所以不要觉得题目简单就跳过把中序遍历的递归、迭代、Morris 三种写法都搞明白后面做题会顺很多。2. 递归解法最直观但别忽略细节2.1 递归的三个要素递归解法是最好理解也最好写的。写递归只要抓住三件事终止条件是什么、返回值是什么、单层递归逻辑要做什么。对于中序遍历来说终止条件很直接当前节点为空直接返回不做任何处理。返回值其实不需要额外设计因为结果用一个外部容器收集就行递归函数本身只负责按顺序把节点值塞进去。单层逻辑就是左中右三步。2.2 C 递归实现class Solution { public: vectorint inorderTraversal(TreeNode* root) { vectorint res; inorder(root, res); return res; } private: void inorder(TreeNode* root, vectorint res) { if (root nullptr) return; inorder(root-left, res); res.push_back(root-val); inorder(root-right, res); } };这个写法里有一个值得强调的细节res 必须用引用传递。如果把参数改成vectorint res每次递归调用都会拷贝一份当前结果一是白白增加时间和内存二是在多次调用场景下容易导致异常行为甚至超时。我在实际练习中真的见过有人这么传值结果跑大数据用例时性能差得离谱。拷贝容器的代价比你想象的大每个节点都会触发一次 vector 的增长和赋值。2.3 一步步跟踪递归调用拿上面那棵搜索树举例调用顺序是这样的从根节点 4 进入先递归左子树左子树根是 2继续递归 2 的左子树直到节点 1 的 left 为空递归返回然后访问 1再递归 1 的 right 为空返回此时回到节点 2访问 2再递归右子树 33 处理完后回到 4访问 4再进入右子树 6。整个顺序正好是左中右。理解这个调用栈对后面写迭代版本非常有帮助因为迭代版本本质上就是用一个栈模拟这套递归调用过程。2.4 递归的真正软肋代码短不代表没有隐患。递归依赖系统调用栈每一次递归调用都会压栈。如果二叉树退化成一条单链比如每个节点只有右孩子深度是 n那么递归深度也会是 n。当 n 达到十万、百万级别时系统栈很可能会栈溢出程序直接崩掉。这一点在 OJ 上有些极端测试用例里能真实触发。C 本身对递归也没有尾递归优化写递归就只能靠系统栈。所以递归虽然简单却是“看似普通但不适合极限场景”的方案这也是为什么后续要学迭代写法和 Morris 遍历。3. 迭代解法用显式栈模拟系统调用栈3.1 迭代的必要性递归的本质是系统帮你维护了一个“调用栈”。迭代写法就是把那个栈显式地放在自己手里空间可控也不依赖系统栈深度。面试中如果你能从递归切换到迭代并且讲清楚两者之间的关系通常会加分因为这说明你不只是背代码而是理解了底层机制。还有一个附带好处迭代版本对树的破坏性小写完不需要像递归那样担心栈爆。3.2 核心模板左链入栈法迭代中序遍历有一个经典写法一路往左下走把路上所有节点都压入栈压到空节点后弹出栈顶访问然后把指针转向右子树继续执行“一路往左下压”的过程。这个思路有个口诀“有左就压左没了弹出来访问然后走右”。注意这里和层序遍历不一样不能用队列。层序遍历用队列是因为它要按层“先进先出”地处理而中序遍历要保证左子树先处理完得用栈的“后进先出”特性先把深层左节点放在栈顶。如果误用队列顺序就变成按层混排完全不是中序。核心逻辑用伪代码写出来就是cur root 创建栈 s while cur ! null 或 s 不为空: while cur ! null: s.push(cur) cur cur-left cur s.top(); s.pop() 访问 cur-val cur cur-right为什么这个流程能保证左根右关键在于每次从栈里弹出来的节点它的左子树要么为空要么已经被完整处理过了。由于入栈时一路压左链弹栈顺序和递归里的“返回到上一层”是一致的。弹完当前节点后立刻把 cur 设为它的右孩子下一轮循环会继续处理右子树。3.3 完整实现代码class Solution { public: vectorint inorderTraversal(TreeNode* root) { vectorint res; stackTreeNode* stk; TreeNode* cur root; while (cur ! nullptr || !stk.empty()) { while (cur ! nullptr) { stk.push(cur); cur cur-left; } cur stk.top(); stk.pop(); res.push_back(cur-val); cur cur-right; } return res; } };3.4 用例子完整走一遍栈还是用 4 2 6 1 3 5 7 那棵树初始 cur4stk 空。第一轮内层 while压 4cur2压 2cur1压 1curnullptr。然后弹出 1访问cur1-rightnullptr。外层循环继续cur 为 null 但 stk 非空不进入内层 while弹出 2访问cur2-right3。下一轮压 3 并弹出访问接着回到 4先后处理右子树 6、5、7。看到没整个输出就是 1 2 3 4 5 6 7。这里有个细节值得注意内层 while 一旦把 cur 置为空就表示当前栈顶的左子树已经处理完了接下来每次弹出就是一个“根”节点。弹完以后只需要让 cur 指向 right右子树会在后续循环里继续经历同样的压左链过程。3.5 迭代写法的常见错误第一个常见错误内层 while 写成把空节点也压栈。比如有些人会先把 root 压栈再循环里不管左右是否为空都 push。这种写法容易导致循环条件判断变得复杂而且空节点参与运算会让代码里到处都要判空。上面这个模板刻意只在 cur 非空时才压栈空节点天然被跳过逻辑干净。第二个常见错误弹出一个节点后马上把它的右孩子也压栈但忘记重新进入内层 while 去深入右孩子的左子树。如果你直接把右孩子压栈右子树自身还有左子树的时候顺序就错了。正确做法是把 cur 指向右孩子让外层循环的下一次迭代去决定要不要继续压左链而不是手动压右孩子。第三个常见错误外层循环条件写成while (!stk.empty())然后单独处理 cur 为空。斜树场景没问题但普通树在处理完左链后 cur 可能为空而栈非空这时逻辑能继续可当右子树处理完且栈为空、cur 也为空时循环条件不满足正好退出。如果是while (!stk.empty())当 cur 存在但栈为空时比如遍历到根节点后栈刚弹空但 cur 指向右孩子非空会提前退出。所以外层条件一定要写成cur ! nullptr || !stk.empty()。4. Morris 中序遍历空间复杂度压到 O(1)4.1 它到底在做什么递归和迭代的空间复杂度都是 O(h)h 是树高。Morris 遍历把空间复杂度降到 O(1)只用一个 cur 指针和一个 prev 指针不借助栈。它的核心思路是“线索化”利用叶子节点空闲的右指针临时记录回溯路径。因为很多节点的右指针本来就是 nullptr放着也是浪费Morris 就把它临时指向中序顺序里的下一个节点访问完再改回来最终仍能恢复树的结构。4.2 中序前驱与“线索”的关系看到这里你就会知道为什么提到中序遍历了对于当前节点 cur它在左子树里最右边的那个节点正好是中序序列里 cur 的前驱。比如 cur4它的左子树是 2 和 3左子树最右节点是 3中序序列 1 2 3 4 里 3 就是 4 的前驱。Morris 的方法就是如果 cur 有左子树先找到这个前驱节点 predecessor把 predecessor 的右指针临时指向 cur这样遍历完左子树之后就能顺着这个指针回到 cur不需要额外的栈来保存回溯信息。4.3 Morris 遍历完整流程流程可以分成四步若 cur 为空终止。若 cur 没有左子树访问 cur然后 cur 移向右孩子。若 cur 有左子树找左子树最右节点 predecessor。若 predecessor 的右指针为空把它的右指针指向 cur然后 cur 移向左孩子。若 predecessor 的右指针已经指向 cur说明左子树已经遍历完了把它的右指针恢复为空访问 cur然后 cur 移向右孩子。这个流程第一次看容易绕但抓住“找前驱、挂线索、复用线索判定是否二次经过”就能捋清楚。关键点在两次经过一个节点时的不同行为第一次经过 cur 时它会向左走并挂线索第二次经过 cur 时说明左子树已经处理完于是断线索并访问 cur然后向右。4.4 C 代码实现class Solution { public: vectorint inorderTraversal(TreeNode* root) { vectorint res; TreeNode* cur root; while (cur ! nullptr) { if (cur-left nullptr) { res.push_back(cur-val); cur cur-right; } else { TreeNode* predecessor cur-left; while (predecessor-right ! nullptr predecessor-right ! cur) { predecessor predecessor-right; } if (predecessor-right nullptr) { predecessor-right cur; cur cur-left; } else { predecessor-right nullptr; res.push_back(cur-val); cur cur-right; } } } return res; } };这段代码有三个地方容易看混。第一找 predecessor 的内层循环条件是predecessor-right ! nullptr predecessor-right ! cur。如果不加第二个条件当线索已经挂上去之后predecessor 的右指针恰好指向 cur循环就会继续跑把之前挂的线索又带歪。第二区分“第一次遇见”和“第二次遇见”靠的是 predecessor-right 是否为 nullptr。第一次为 nullptr挂线索后去左子树第二次不为 nullptr 且等于 cur说明左子树已处理完这时才访问 cur。第三访问节点的位置不是固定的左子树为空时就在原地访问有左子树时在“恢复线索”分支访问整体保证节点只在“左子树处理完之后”被输出。4.5 一步步走一遍 Morris用更小的树 2 - 1, 3 来模拟。初始 cur2有左子树 1predecessor1predecessor-right 为空于是把它指向 2cur1。下一轮 cur1左子树为空访问 1cur 顺着临时指针回到 2。现在 cur2左子树非空找 predecessor从 cur-left节点1找最右节点发现 predecessor-right 已经等于 cur走到 else 分支恢复 predecessor-right 为 nullptr访问 2cur2-right3。下一轮 cur3左子树为空访问 3结束。输出 1 2 3完全正确。可以看到Morris 并没有额外占用栈空间只靠修改几个指针完成了回溯。代价是它临时修改了树的结构虽然最后能恢复但如果树被多线程共享或者题目不允许修改树结构就不能用这个方案。4.6 Morris 的适用场景Morris 遍历在面试中属于比较进阶的写法。优点是空间复杂度 O(1)常数也小缺点是代码难写、难记、出错率高而且会临时改动树。我的建议是理解、能口述、能写出正确代码但不要作为默认首选的方案。一般面试场景下先给递归或迭代再提到 Morris 作为空间优化方案这个节奏比较稳妥。真到实际工程里需要中序遍历又不希望改树还是用迭代或者递归。5. OJ 实战测试用例、复杂度与常见问题5.1 不同写法的复杂度对比把三种解法放一起看递归时间复杂度 O(n)空间复杂度 O(h)最坏 O(n)迭代时间复杂度 O(n)空间复杂度 O(h)最坏 O(n)栈里最多存一条左链极端单链时可以到 nMorris 时间复杂度同样是 O(n)空间 O(1)。Morris 虽然时间渐进复杂度一样但因为每个内部节点可能要多次找前驱实际常数会大一些。解法时间复杂度空间复杂度是否修改树难度递归O(n)O(h)最坏 O(n)否低迭代O(n)O(h)最坏 O(n)否中MorrisO(n)O(1)是但会恢复高注意空间复杂度不能写成 O(1) 的递归因为在评测环境里递归调用会占用真实调用栈极端树深时甚至会栈溢出。有些同学看到题解里写“空间 O(1)”就以为递归也不占空间这是误解。空间复杂度的“额外空间”指的是除了输入和输出之外额外申请的资源递归调用栈是实打实的系统开销。5.2 输入输出细节与本地建树二叉树题目输入通常是一个数组例如[1,null,2,3]转换成二叉树的方式是按层序给出的。具体来说null 表示当前位置没有节点但是用它占住下标让后面的节点能正确挂到父节点下面。比如[1,null,2,3]根节点 1没有左孩子右孩子是 22 的左孩子是 3。在本地调试的时候我习惯手写一个 buildTree 辅助函数用队列按层序建树这样能快速验证算法在特定输入下的表现。TreeNode* buildTree(const vectorint vals) { if (vals.empty()) return nullptr; TreeNode* root new TreeNode(vals[0]); queueTreeNode* q; q.push(root); int i 1; while (i vals.size()) { TreeNode* node q.front(); q.pop(); if (i vals.size() vals[i] ! INT_MIN) { node-left new TreeNode(vals[i]); q.push(node-left); } i; if (i vals.size() vals[i] ! INT_MIN) { node-right new TreeNode(vals[i]); q.push(node-right); } i; } return root; }注意这里我用 INT_MIN 代表空节点或者可以用其它约定关键是和算法代码里的判空逻辑保持一致。OJ 在线编辑器里不需要写建树函数但本地调试时有个能用的建树代码会方便很多。5.3 空树、单节点、斜树的边界测试测试用例里常会出现空树。空树的中序遍历结果就是空 vector。单节点树直接输出节点值。斜树是最容易暴露迭代写法 bug 的测试一棵只有右孩子的链递归会压 n 层栈迭代则能稳定工作只有左孩子的链迭代版本的内层 while 会一直向左压然后从最左边开始依次弹出顺序正确。我自己排查迭代 bug 时固定用五种用例空树、单节点、右斜链、左斜链、普通满树。先跑简单边界再跑复杂树定位问题效率很高。5.4 本地调试的常见问题这一块经常被初学者忽略。最常见的报错是AddressSanitizer: heap-buffer-overflow或者stack overflow。前者多半是你访问了空指针的 val比如 cur 在某个分支变成了 nullptr 但没有判空直接访问后者是树太深、递归爆栈。还有一个隐蔽问题在线平台的 TreeNode 是平台提供的本地写测试时如果忘记释放 new 出来的节点内存检测工具会提示内存泄漏。刷题时可以不释放因为进程退出会自动回收但如果在长任务或服务器环境里这种写法不可取。迭代版本还有一个很容易犯的错弹出的节点是左子树处理完后才访问如果你在压栈的时候就把值 push 进 result输出顺序就变成前序了。判断顺序对不对最直接的办法是拿一棵三层满二叉树跑一遍输出应该是左根右的模式而不是根左右。5.5 从报错到定位的思路报错不要慌按顺序检查先确认建树函数是否按题目数组语义工作尤其处理 null 的索引是否正确再检查算法逻辑用一个只有 3 到 5 个节点的树手动推演最后加上打印调试观察每轮 cur 指针到了哪个节点、栈的大小。定位中序 bug 的核心原则是验证“左子树是否完整处理完才访问根节点”。只要这个顺序不对问题一定出在循环流程或者递归函数的调用顺序上。6. 从这道题延伸出去的东西6.1 面试答这道题的正确节奏如果面试官让你写中序遍历不要直接甩一个递归上去就完事。一个不错的回答思路是先说明中序遍历的顺序是左根右给出递归版本然后说递归有栈溢出风险所以给出迭代版本再顺势引出 Morris说明它能做到 O(1) 空间但不推荐在生产环境修改树。把三种方案都讲一遍面试官基本能确认你对二叉树遍历的理解深度。关键不是代码有多长而是你能不能在讲代码的同时把时间复杂度和空间复杂度说清楚。6.2 中序遍历的直接延展掌握中序遍历之后可以马上试试这些变体验证二叉搜索树只需要检查中序遍历结果是否严格递增找第 k 小的元素中序遍历走到第 k 个就能停止找二叉搜索树的两个错误交换节点对比中序遍历的逆序对。如果你能把这道题做到三种写法都能默写这些扩展题解决起来会轻松很多。中序遍历的框架本身也是一个“左中右”的模板任何需要按中序顺序处理节点的问题都可以在这个模板上改。6.3 一个树形结构的小细节二叉树遍历里很多同学会把“中序”和“二叉搜索树”绑得太紧以至于忘了中序遍历本身适用于任意二叉树。其实中序遍历只规定顺序不要求二叉搜索树。对一个普通二叉树中序输出的结果没有递增特性但依然是合法的遍历。理解这一点有助于你在做“恢复二叉搜索树”时不会误以为输出必须有序是树的定义。树的结构决定了遍历顺序而不是反过来。6.4 我踩过的坑最后说个我自己印象很深的坑。最开始我学迭代中序网上看到一个模板是“先把根入栈然后 while 栈不为空取栈顶如果有左孩子就入左孩子……”这个写法看起来很合理实际对中序根本是错的。因为它没有区分“左子树是否处理完”。根节点第一次被看到时左子树还没处理但你在栈顶已经遇到它如果此时访问输出的就是前序。后来我才明白标准的左链入栈法为什么要在弹出时才访问因为弹出的时刻才代表“左子树已经全部处理完”。这个经验之后在做迭代后序遍历时也帮了我记住一句话栈顶不等于“可以访问”只有出栈顺序和递归返回顺序一致时才可以。 二叉树中序遍历全解：递归、迭代与Morris遍历的C++实现
刷 LeetCode 的时候很多人第一道二叉树题做的都是中序遍历。这题表面上看着特别基础递归写法十来行就能完事可一旦较真起来会发现里面藏着不少东西。中序遍历是二叉树三种深度优先遍历里唯一能天然保持“左子树全部处理完再来根节点最后右子树”这种严格顺序的遍历方式而正是这个顺序让它在二叉搜索树的处理上拥有不可替代的地位。本文用 C 把递归、迭代和 Morris 线索化三种解法全部过一遍逐个分析原理、时间空间复杂度再把 OJ 上容易踩的坑一个个点出来。不管你是刚接触二叉树的新手还是准备面试需要系统梳理的老手这篇文章都能给出可以直接参考的实现方案。1. 题目拆解中序遍历到底在遍历什么1.1 题目原题与基本约定先看题面给一棵二叉树的根节点 root返回它的中序遍历结果。OJ 上要求返回一个vectorint元素顺序就是中序遍历访问节点的顺序。这里的二叉树节点定义是标准的三件套struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} };这个定义在二叉树相关题目里几乎是统一模板三个构造函数分别对应默认构造、只给值和完整构造。实际刷题时你通常不需要自己构造 TreeNode因为平台已经做好了建树和传参但理解它的结构很重要val 是节点值left 和 right 是指向下一个节点的指针叶子节点的左右指针都是 nullptr。1.2 前序、中序、后序的遍历顺序二叉树的深度优先遍历有三种顺序区别只在于“根节点什么时候被访问”。前序遍历是根左右中序遍历是左根右后序遍历是左右根。很多初学者容易记混我习惯用“根在哪个位置”来记忆根在前就是前序根在中间就是中序根在最后就是后序。三个名字描述的是根节点在整棵子树的访问时机并不是说左子树和右子树的相对顺序会变。中序遍历的执行过程可以描述为递归遍历左子树访问当前根节点递归遍历右子树。这个“左根右”的顺序在一个二叉搜索树上会呈现一个非常有规律的结果。举个例子一棵搜索树4 / \ 2 6 / \ / \ 1 3 5 7中序遍历输出是 1 2 3 4 5 6 7正好是排序后的序列。这不是巧合而是二叉搜索树的中序遍历天然有序这个性质在后面解决“验证二叉搜索树”“寻找第 k 小元素”等题目时是核心抓手。1.3 为什么单独拿中序遍历讲前序和后序更多用于树的构建、序列化、表达式求值等场景而中序因为“天然有序”这个特点在面试和算法题里被用得最多。这道题作为最基础的一道本质上是给下面一系列题目打底验证二叉搜索树、二叉树中第 k 小的元素、二叉搜索树的最小绝对差、恢复二叉搜索树等等全都是在中序遍历结果上做文章。所以不要觉得题目简单就跳过把中序遍历的递归、迭代、Morris 三种写法都搞明白后面做题会顺很多。2. 递归解法最直观但别忽略细节2.1 递归的三个要素递归解法是最好理解也最好写的。写递归只要抓住三件事终止条件是什么、返回值是什么、单层递归逻辑要做什么。对于中序遍历来说终止条件很直接当前节点为空直接返回不做任何处理。返回值其实不需要额外设计因为结果用一个外部容器收集就行递归函数本身只负责按顺序把节点值塞进去。单层逻辑就是左中右三步。2.2 C 递归实现class Solution { public: vectorint inorderTraversal(TreeNode* root) { vectorint res; inorder(root, res); return res; } private: void inorder(TreeNode* root, vectorint res) { if (root nullptr) return; inorder(root-left, res); res.push_back(root-val); inorder(root-right, res); } };这个写法里有一个值得强调的细节res 必须用引用传递。如果把参数改成vectorint res每次递归调用都会拷贝一份当前结果一是白白增加时间和内存二是在多次调用场景下容易导致异常行为甚至超时。我在实际练习中真的见过有人这么传值结果跑大数据用例时性能差得离谱。拷贝容器的代价比你想象的大每个节点都会触发一次 vector 的增长和赋值。2.3 一步步跟踪递归调用拿上面那棵搜索树举例调用顺序是这样的从根节点 4 进入先递归左子树左子树根是 2继续递归 2 的左子树直到节点 1 的 left 为空递归返回然后访问 1再递归 1 的 right 为空返回此时回到节点 2访问 2再递归右子树 33 处理完后回到 4访问 4再进入右子树 6。整个顺序正好是左中右。理解这个调用栈对后面写迭代版本非常有帮助因为迭代版本本质上就是用一个栈模拟这套递归调用过程。2.4 递归的真正软肋代码短不代表没有隐患。递归依赖系统调用栈每一次递归调用都会压栈。如果二叉树退化成一条单链比如每个节点只有右孩子深度是 n那么递归深度也会是 n。当 n 达到十万、百万级别时系统栈很可能会栈溢出程序直接崩掉。这一点在 OJ 上有些极端测试用例里能真实触发。C 本身对递归也没有尾递归优化写递归就只能靠系统栈。所以递归虽然简单却是“看似普通但不适合极限场景”的方案这也是为什么后续要学迭代写法和 Morris 遍历。3. 迭代解法用显式栈模拟系统调用栈3.1 迭代的必要性递归的本质是系统帮你维护了一个“调用栈”。迭代写法就是把那个栈显式地放在自己手里空间可控也不依赖系统栈深度。面试中如果你能从递归切换到迭代并且讲清楚两者之间的关系通常会加分因为这说明你不只是背代码而是理解了底层机制。还有一个附带好处迭代版本对树的破坏性小写完不需要像递归那样担心栈爆。3.2 核心模板左链入栈法迭代中序遍历有一个经典写法一路往左下走把路上所有节点都压入栈压到空节点后弹出栈顶访问然后把指针转向右子树继续执行“一路往左下压”的过程。这个思路有个口诀“有左就压左没了弹出来访问然后走右”。注意这里和层序遍历不一样不能用队列。层序遍历用队列是因为它要按层“先进先出”地处理而中序遍历要保证左子树先处理完得用栈的“后进先出”特性先把深层左节点放在栈顶。如果误用队列顺序就变成按层混排完全不是中序。核心逻辑用伪代码写出来就是cur root 创建栈 s while cur ! null 或 s 不为空: while cur ! null: s.push(cur) cur cur-left cur s.top(); s.pop() 访问 cur-val cur cur-right为什么这个流程能保证左根右关键在于每次从栈里弹出来的节点它的左子树要么为空要么已经被完整处理过了。由于入栈时一路压左链弹栈顺序和递归里的“返回到上一层”是一致的。弹完当前节点后立刻把 cur 设为它的右孩子下一轮循环会继续处理右子树。3.3 完整实现代码class Solution { public: vectorint inorderTraversal(TreeNode* root) { vectorint res; stackTreeNode* stk; TreeNode* cur root; while (cur ! nullptr || !stk.empty()) { while (cur ! nullptr) { stk.push(cur); cur cur-left; } cur stk.top(); stk.pop(); res.push_back(cur-val); cur cur-right; } return res; } };3.4 用例子完整走一遍栈还是用 4 2 6 1 3 5 7 那棵树初始 cur4stk 空。第一轮内层 while压 4cur2压 2cur1压 1curnullptr。然后弹出 1访问cur1-rightnullptr。外层循环继续cur 为 null 但 stk 非空不进入内层 while弹出 2访问cur2-right3。下一轮压 3 并弹出访问接着回到 4先后处理右子树 6、5、7。看到没整个输出就是 1 2 3 4 5 6 7。这里有个细节值得注意内层 while 一旦把 cur 置为空就表示当前栈顶的左子树已经处理完了接下来每次弹出就是一个“根”节点。弹完以后只需要让 cur 指向 right右子树会在后续循环里继续经历同样的压左链过程。3.5 迭代写法的常见错误第一个常见错误内层 while 写成把空节点也压栈。比如有些人会先把 root 压栈再循环里不管左右是否为空都 push。这种写法容易导致循环条件判断变得复杂而且空节点参与运算会让代码里到处都要判空。上面这个模板刻意只在 cur 非空时才压栈空节点天然被跳过逻辑干净。第二个常见错误弹出一个节点后马上把它的右孩子也压栈但忘记重新进入内层 while 去深入右孩子的左子树。如果你直接把右孩子压栈右子树自身还有左子树的时候顺序就错了。正确做法是把 cur 指向右孩子让外层循环的下一次迭代去决定要不要继续压左链而不是手动压右孩子。第三个常见错误外层循环条件写成while (!stk.empty())然后单独处理 cur 为空。斜树场景没问题但普通树在处理完左链后 cur 可能为空而栈非空这时逻辑能继续可当右子树处理完且栈为空、cur 也为空时循环条件不满足正好退出。如果是while (!stk.empty())当 cur 存在但栈为空时比如遍历到根节点后栈刚弹空但 cur 指向右孩子非空会提前退出。所以外层条件一定要写成cur ! nullptr || !stk.empty()。4. Morris 中序遍历空间复杂度压到 O(1)4.1 它到底在做什么递归和迭代的空间复杂度都是 O(h)h 是树高。Morris 遍历把空间复杂度降到 O(1)只用一个 cur 指针和一个 prev 指针不借助栈。它的核心思路是“线索化”利用叶子节点空闲的右指针临时记录回溯路径。因为很多节点的右指针本来就是 nullptr放着也是浪费Morris 就把它临时指向中序顺序里的下一个节点访问完再改回来最终仍能恢复树的结构。4.2 中序前驱与“线索”的关系看到这里你就会知道为什么提到中序遍历了对于当前节点 cur它在左子树里最右边的那个节点正好是中序序列里 cur 的前驱。比如 cur4它的左子树是 2 和 3左子树最右节点是 3中序序列 1 2 3 4 里 3 就是 4 的前驱。Morris 的方法就是如果 cur 有左子树先找到这个前驱节点 predecessor把 predecessor 的右指针临时指向 cur这样遍历完左子树之后就能顺着这个指针回到 cur不需要额外的栈来保存回溯信息。4.3 Morris 遍历完整流程流程可以分成四步若 cur 为空终止。若 cur 没有左子树访问 cur然后 cur 移向右孩子。若 cur 有左子树找左子树最右节点 predecessor。若 predecessor 的右指针为空把它的右指针指向 cur然后 cur 移向左孩子。若 predecessor 的右指针已经指向 cur说明左子树已经遍历完了把它的右指针恢复为空访问 cur然后 cur 移向右孩子。这个流程第一次看容易绕但抓住“找前驱、挂线索、复用线索判定是否二次经过”就能捋清楚。关键点在两次经过一个节点时的不同行为第一次经过 cur 时它会向左走并挂线索第二次经过 cur 时说明左子树已经处理完于是断线索并访问 cur然后向右。4.4 C 代码实现class Solution { public: vectorint inorderTraversal(TreeNode* root) { vectorint res; TreeNode* cur root; while (cur ! nullptr) { if (cur-left nullptr) { res.push_back(cur-val); cur cur-right; } else { TreeNode* predecessor cur-left; while (predecessor-right ! nullptr predecessor-right ! cur) { predecessor predecessor-right; } if (predecessor-right nullptr) { predecessor-right cur; cur cur-left; } else { predecessor-right nullptr; res.push_back(cur-val); cur cur-right; } } } return res; } };这段代码有三个地方容易看混。第一找 predecessor 的内层循环条件是predecessor-right ! nullptr predecessor-right ! cur。如果不加第二个条件当线索已经挂上去之后predecessor 的右指针恰好指向 cur循环就会继续跑把之前挂的线索又带歪。第二区分“第一次遇见”和“第二次遇见”靠的是 predecessor-right 是否为 nullptr。第一次为 nullptr挂线索后去左子树第二次不为 nullptr 且等于 cur说明左子树已处理完这时才访问 cur。第三访问节点的位置不是固定的左子树为空时就在原地访问有左子树时在“恢复线索”分支访问整体保证节点只在“左子树处理完之后”被输出。4.5 一步步走一遍 Morris用更小的树 2 - 1, 3 来模拟。初始 cur2有左子树 1predecessor1predecessor-right 为空于是把它指向 2cur1。下一轮 cur1左子树为空访问 1cur 顺着临时指针回到 2。现在 cur2左子树非空找 predecessor从 cur-left节点1找最右节点发现 predecessor-right 已经等于 cur走到 else 分支恢复 predecessor-right 为 nullptr访问 2cur2-right3。下一轮 cur3左子树为空访问 3结束。输出 1 2 3完全正确。可以看到Morris 并没有额外占用栈空间只靠修改几个指针完成了回溯。代价是它临时修改了树的结构虽然最后能恢复但如果树被多线程共享或者题目不允许修改树结构就不能用这个方案。4.6 Morris 的适用场景Morris 遍历在面试中属于比较进阶的写法。优点是空间复杂度 O(1)常数也小缺点是代码难写、难记、出错率高而且会临时改动树。我的建议是理解、能口述、能写出正确代码但不要作为默认首选的方案。一般面试场景下先给递归或迭代再提到 Morris 作为空间优化方案这个节奏比较稳妥。真到实际工程里需要中序遍历又不希望改树还是用迭代或者递归。5. OJ 实战测试用例、复杂度与常见问题5.1 不同写法的复杂度对比把三种解法放一起看递归时间复杂度 O(n)空间复杂度 O(h)最坏 O(n)迭代时间复杂度 O(n)空间复杂度 O(h)最坏 O(n)栈里最多存一条左链极端单链时可以到 nMorris 时间复杂度同样是 O(n)空间 O(1)。Morris 虽然时间渐进复杂度一样但因为每个内部节点可能要多次找前驱实际常数会大一些。解法时间复杂度空间复杂度是否修改树难度递归O(n)O(h)最坏 O(n)否低迭代O(n)O(h)最坏 O(n)否中MorrisO(n)O(1)是但会恢复高注意空间复杂度不能写成 O(1) 的递归因为在评测环境里递归调用会占用真实调用栈极端树深时甚至会栈溢出。有些同学看到题解里写“空间 O(1)”就以为递归也不占空间这是误解。空间复杂度的“额外空间”指的是除了输入和输出之外额外申请的资源递归调用栈是实打实的系统开销。5.2 输入输出细节与本地建树二叉树题目输入通常是一个数组例如[1,null,2,3]转换成二叉树的方式是按层序给出的。具体来说null 表示当前位置没有节点但是用它占住下标让后面的节点能正确挂到父节点下面。比如[1,null,2,3]根节点 1没有左孩子右孩子是 22 的左孩子是 3。在本地调试的时候我习惯手写一个 buildTree 辅助函数用队列按层序建树这样能快速验证算法在特定输入下的表现。TreeNode* buildTree(const vectorint vals) { if (vals.empty()) return nullptr; TreeNode* root new TreeNode(vals[0]); queueTreeNode* q; q.push(root); int i 1; while (i vals.size()) { TreeNode* node q.front(); q.pop(); if (i vals.size() vals[i] ! INT_MIN) { node-left new TreeNode(vals[i]); q.push(node-left); } i; if (i vals.size() vals[i] ! INT_MIN) { node-right new TreeNode(vals[i]); q.push(node-right); } i; } return root; }注意这里我用 INT_MIN 代表空节点或者可以用其它约定关键是和算法代码里的判空逻辑保持一致。OJ 在线编辑器里不需要写建树函数但本地调试时有个能用的建树代码会方便很多。5.3 空树、单节点、斜树的边界测试测试用例里常会出现空树。空树的中序遍历结果就是空 vector。单节点树直接输出节点值。斜树是最容易暴露迭代写法 bug 的测试一棵只有右孩子的链递归会压 n 层栈迭代则能稳定工作只有左孩子的链迭代版本的内层 while 会一直向左压然后从最左边开始依次弹出顺序正确。我自己排查迭代 bug 时固定用五种用例空树、单节点、右斜链、左斜链、普通满树。先跑简单边界再跑复杂树定位问题效率很高。5.4 本地调试的常见问题这一块经常被初学者忽略。最常见的报错是AddressSanitizer: heap-buffer-overflow或者stack overflow。前者多半是你访问了空指针的 val比如 cur 在某个分支变成了 nullptr 但没有判空直接访问后者是树太深、递归爆栈。还有一个隐蔽问题在线平台的 TreeNode 是平台提供的本地写测试时如果忘记释放 new 出来的节点内存检测工具会提示内存泄漏。刷题时可以不释放因为进程退出会自动回收但如果在长任务或服务器环境里这种写法不可取。迭代版本还有一个很容易犯的错弹出的节点是左子树处理完后才访问如果你在压栈的时候就把值 push 进 result输出顺序就变成前序了。判断顺序对不对最直接的办法是拿一棵三层满二叉树跑一遍输出应该是左根右的模式而不是根左右。5.5 从报错到定位的思路报错不要慌按顺序检查先确认建树函数是否按题目数组语义工作尤其处理 null 的索引是否正确再检查算法逻辑用一个只有 3 到 5 个节点的树手动推演最后加上打印调试观察每轮 cur 指针到了哪个节点、栈的大小。定位中序 bug 的核心原则是验证“左子树是否完整处理完才访问根节点”。只要这个顺序不对问题一定出在循环流程或者递归函数的调用顺序上。6. 从这道题延伸出去的东西6.1 面试答这道题的正确节奏如果面试官让你写中序遍历不要直接甩一个递归上去就完事。一个不错的回答思路是先说明中序遍历的顺序是左根右给出递归版本然后说递归有栈溢出风险所以给出迭代版本再顺势引出 Morris说明它能做到 O(1) 空间但不推荐在生产环境修改树。把三种方案都讲一遍面试官基本能确认你对二叉树遍历的理解深度。关键不是代码有多长而是你能不能在讲代码的同时把时间复杂度和空间复杂度说清楚。6.2 中序遍历的直接延展掌握中序遍历之后可以马上试试这些变体验证二叉搜索树只需要检查中序遍历结果是否严格递增找第 k 小的元素中序遍历走到第 k 个就能停止找二叉搜索树的两个错误交换节点对比中序遍历的逆序对。如果你能把这道题做到三种写法都能默写这些扩展题解决起来会轻松很多。中序遍历的框架本身也是一个“左中右”的模板任何需要按中序顺序处理节点的问题都可以在这个模板上改。6.3 一个树形结构的小细节二叉树遍历里很多同学会把“中序”和“二叉搜索树”绑得太紧以至于忘了中序遍历本身适用于任意二叉树。其实中序遍历只规定顺序不要求二叉搜索树。对一个普通二叉树中序输出的结果没有递增特性但依然是合法的遍历。理解这一点有助于你在做“恢复二叉搜索树”时不会误以为输出必须有序是树的定义。树的结构决定了遍历顺序而不是反过来。6.4 我踩过的坑最后说个我自己印象很深的坑。最开始我学迭代中序网上看到一个模板是“先把根入栈然后 while 栈不为空取栈顶如果有左孩子就入左孩子……”这个写法看起来很合理实际对中序根本是错的。因为它没有区分“左子树是否处理完”。根节点第一次被看到时左子树还没处理但你在栈顶已经遇到它如果此时访问输出的就是前序。后来我才明白标准的左链入栈法为什么要在弹出时才访问因为弹出的时刻才代表“左子树已经全部处理完”。这个经验之后在做迭代后序遍历时也帮了我记住一句话栈顶不等于“可以访问”只有出栈顺序和递归返回顺序一致时才可以。