刷 LeetCode 的时候，很多人第一道二叉树题做的都是中序遍历。这题表面上看着特别基础，递归写法十来行就能完事，可一旦较真起来，会发现里面藏着不少东西。中序遍历是二叉树三种深度优先遍历里唯一能天然保持“左子树全部处理完，再来根节点，最后右子树”这种严格顺序的遍历方式，而正是这个顺序，让它在二叉搜索树的处理上拥有不可替代的地位。本文用 C++ 把递归、迭代和 Morris 线索化三种解法全部过一遍，逐个分析原理、时间空间复杂度，再把 OJ 上容易踩的坑一个个点出来。不管你是刚接触二叉树的新手，还是准备面试需要系统梳理的老手，这篇文章都能给出可以直接参考的实现方案。
1. 题目拆解：中序遍历到底在遍历什么
1.1 题目原题与基本约定
先看题面：给一棵二叉树的根节点 root，返回它的中序遍历结果。OJ 上要求返回一个vector<int>，元素顺序就是中序遍历访问节点的顺序。这里的二叉树节点定义是标准的三件套：
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: vector<int> inorderTraversal(TreeNode* root) { vector<int> res; inorder(root, res); return res; } private: void inorder(TreeNode* root, vector<int>& res) { if (root == nullptr) return; inorder(root->left, res); res.push_back(root->val); inorder(root->right, res); } };这个写法里有一个值得强调的细节：res 必须用引用传递。如果把参数改成vector<int> res，每次递归调用都会拷贝一份当前结果，一是白白增加时间和内存，二是在多次调用场景下容易导致异常行为，甚至超时。我在实际练习中真的见过有人这么传值，结果跑大数据用例时性能差得离谱。拷贝容器的代价比你想象的大，每个节点都会触发一次 vector 的增长和赋值。
2.3 一步步跟踪递归调用
拿上面那棵搜索树举例，调用顺序是这样的：从根节点 4 进入，先递归左子树，左子树根是 2；继续递归 2 的左子树，直到节点 1 的 left 为空，递归返回，然后访问 1，再递归 1 的 right 为空返回；此时回到节点 2，访问 2，再递归右子树 3；3 处理完后回到 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: vector<int> inorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> 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 那棵树，初始 cur=4，stk 空。第一轮内层 while：压 4，cur=2；压 2，cur=1；压 1，cur=nullptr。然后弹出 1，访问，cur=1->right=nullptr。外层循环继续，cur 为 null 但 stk 非空，不进入内层 while，弹出 2，访问，cur=2->right=3。下一轮压 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 的前驱。比如 cur=4，它的左子树是 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: vector<int> inorderTraversal(TreeNode* root) { vector<int> 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 来模拟。初始 cur=2，有左子树 1，predecessor=1，predecessor->right 为空，于是把它指向 2，cur=1。下一轮 cur=1，左子树为空，访问 1，cur 顺着临时指针回到 2。现在 cur=2，左子树非空，找 predecessor：从 cur->left（节点1）找最右节点，发现 predecessor->right 已经等于 cur，走到 else 分支，恢复 predecessor->right 为 nullptr，访问 2，cur=2->right=3。下一轮 cur=3，左子树为空，访问 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)（栈里最多存一条左链，极端单链时可以到 n）；Morris 时间复杂度同样是 O(n)，空间 O(1)。Morris 虽然时间渐进复杂度一样，但因为每个内部节点可能要多次找前驱，实际常数会大一些。
| 解法 | 时间复杂度 | 空间复杂度 | 是否修改树 | 难度 |
|---|---|---|---|---|
| 递归 | O(n) | O(h)，最坏 O(n) | 否 | 低 |
| 迭代 | O(n) | O(h)，最坏 O(n) | 否 | 中 |
| Morris | O(n) | O(1) | 是（但会恢复） | 高 |
注意空间复杂度不能写成 O(1) 的递归，因为在评测环境里递归调用会占用真实调用栈，极端树深时甚至会栈溢出。有些同学看到题解里写“空间 O(1)”就以为递归也不占空间，这是误解。空间复杂度的“额外空间”指的是除了输入和输出之外额外申请的资源，递归调用栈是实打实的系统开销。
5.2 输入输出细节与本地建树
二叉树题目，输入通常是一个数组，例如[1,null,2,3]，转换成二叉树的方式是按层序给出的。具体来说，null 表示当前位置没有节点，但是用它占住下标，让后面的节点能正确挂到父节点下面。比如[1,null,2,3]，根节点 1，没有左孩子，右孩子是 2，2 的左孩子是 3。在本地调试的时候，我习惯手写一个 buildTree 辅助函数，用队列按层序建树，这样能快速验证算法在特定输入下的表现。
TreeNode* buildTree(const vector<int>& vals) { if (vals.empty()) return nullptr; TreeNode* root = new TreeNode(vals[0]); queue<TreeNode*> 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 栈不为空，取栈顶，如果有左孩子就入左孩子……”这个写法看起来很合理，实际对中序根本是错的。因为它没有区分“左子树是否处理完”。根节点第一次被看到时左子树还没处理，但你在栈顶已经遇到它，如果此时访问，输出的就是前序。后来我才明白，标准的左链入栈法为什么要在弹出时才访问：因为弹出的时刻，才代表“左子树已经全部处理完”。这个经验之后在做迭代后序遍历时也帮了我，记住一句话：栈顶不等于“可以访问”，只有出栈顺序和递归返回顺序一致时才可以。
