企业官网建设流程全解析

• 教程
• 文档
• 知识库

本篇技术指南围绕「算法通关手册」AlgoNote 仓库中的经典题解 0094. 二叉树的中序遍历 展开，系统讲解二叉树中序遍历的「左子树 → 根节点 → 右子树」访问规则，并给出递归与显式栈迭代两种完整可运行的 Python 实现。读完本文，你将掌握中序遍历的递归模板、非递归模拟系统栈的关键技巧，理解其在二叉搜索树（BST）有序序列生成、求第 K 小元素等高频场景中的应用，并能与同仓库的前序、后序遍历解法横向对比。

1. 题目理解：LeetCode 0094 要求什么

1.1 题目大意

给定一个二叉树的根节点root，要求返回该二叉树的中序遍历结果。

中序遍历遵循「左子树 → 根节点 → 右子树」的访问顺序：先递归遍历左子树，再访问当前根节点，最后递归遍历右子树。只要严格遵循这一顺序，无论子树多深，最终输出的节点值序列都是中序序列。

1.2 数据范围与约束

空树（root = []）属于合法输入，返回值应为空列表[]。

1.3 示例

示例 1：

输入：root = [1,null,2,3] 输出：[1,3,2]

该树结构为：根节点1，右子树根节点2，2的左孩子为3。按中序顺序遍历得到1 → 3 → 2。

示例 2：

输入：root = [] 输出：[]

2. 解题思路 1：递归遍历

2.1 算法思想

二叉树本身具有递归结构（根节点 + 左子树 + 右子树），因此中序遍历可以自然地用递归实现。递归实现步骤为：

1. 判断二叉树是否为空，为空则直接返回（递归终止条件）。
2. 先递归遍历左子树。
3. 然后访问根节点（将root.val加入结果列表）。
4. 最后递归遍历右子树。

关键在于"访问根节点"这一操作的位置：它被放在左子树递归调用之后、右子树递归调用之前，这正是中序遍历区别于前序（根在最前）与后序（根在最后）的本质所在。

2.2 代码实现

class Solution: def inorderTraversal(self, root: TreeNode) -> List[int]: res = [] def inorder(root): if not root: return inorder(root.left) # 1. 递归遍历左子树 res.append(root.val) # 2. 访问根节点 inorder(root.right) # 3. 递归遍历右子树 inorder(root) return res

这段代码与仓库中 二叉树的遍历教程 的中序遍历递归实现（3.1 节）结构一致：内部嵌套函数inorder负责递归，res列表闭包共享，实现最简、最不易出错，是面试中最推荐的写法。

2.3 复杂度分析

• 时间复杂度：$O(n)$。每个节点恰好被访问一次，其中 $n$ 是二叉树的节点数目。
• 空间复杂度：$O(n)$。递归调用栈的深度等于树的高度 $h$，最坏情况下树退化为单链表，栈深度为 $O(n)$；结果数组同样占用 $O(n)$ 空间。

3. 解题思路 2：显式栈迭代遍历

3.1 算法思想

递归实现依赖系统调用栈，我们也可以使用一个显式栈stack手动模拟整个递归过程，从而避免递归深度过大带来的栈溢出风险。

核心难点：与前序遍历不同，中序遍历要求"访问根节点"必须发生在左子树全部遍历完之后。因此必须保证——在左子树访问完成之前，当前节点不能提前出栈。

具体做法：

1. 判断二叉树是否为空，为空则直接返回。
2. 初始化一个空栈stack。
3. 当根节点或栈不为空时循环执行：
   • 若当前节点不为空：循环遍历左子树，不断将当前子树的根节点入栈，直到到达最左侧节点；
   • 若当前节点为空：说明已无左子树，此时弹出栈顶元素node并访问它，然后转向node的右子树，重复上述循环。

这个流程保证：节点在左子树完全入栈之后才出栈并被访问，输出严格符合「左 → 根 → 右」的中序顺序。仓库教程 二叉树的遍历教程 的 3.2 节使用了独立的cur指针变量承载"当前节点"，语义上更清晰，而本题解直接用root变量复用指针，逻辑完全等价。

3.2 代码实现

class Solution: def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]: if not root: # 二叉树为空直接返回 return [] res = [] stack = [] while root or stack: # 根节点或栈不为空 while root: stack.append(root) # 将当前树的根节点入栈 root = root.left # 找到最左侧节点 node = stack.pop() # 遍历到最左侧，当前节点无左子树时，将最左侧节点弹出 res.append(node.val) # 访问该节点 root = node.right # 尝试访问该节点的右子树 return res

3.3 复杂度分析

• 时间复杂度：$O(n)$。每个节点入栈一次、出栈一次，总操作次数与节点数 $n$ 线性相关。
• 空间复杂度：$O(n)$。栈中最多同时存放树的高度 $h$ 个节点，最坏情况（链状树）为 $O(n)$。

4. 两种思路对比与选型建议

两者的时间与空间复杂度完全一致。选型建议：笔试/面试优先写递归，代码简洁不易出错；若题目明确要求非递归，或树深度可能超过递归栈限制（如 $10^4$ 量级节点且呈链状），则应采用显式栈迭代写法。

5. 中序遍历的经典应用：二叉搜索树有序序列

中序遍历最有价值的应用场景是二叉搜索树（BST）。根据 BST 性质——左子树所有节点值 < 根节点值 < 右子树所有节点值（详见仓库 二叉搜索树基础教程），对 BST 做中序遍历得到的节点值序列必然是严格递增的。

这一性质衍生出大量高频题目，例如仓库中的经典题解 0230. 二叉搜索树中第 K 小的元素 就采用了中序遍历方案：

class Solution: def kthSmallest(self, root: Optional[TreeNode], k: int) -> int: self.count = 0 # 计数器，记录当前访问的节点序号 self.result = 0 # 存储结果 def inorder_traversal(node): if not node: return inorder_traversal(node.left) # 遍历左子树 self.count += 1 # 访问根节点，计数 +1 if self.count == k: self.result = node.val return inorder_traversal(node.right) # 遍历右子树 inorder_traversal(root) return self.result

该解法的时间复杂度为 $O(k)$（找到第 $k$ 个节点即提前返回，无需遍历完整棵树），空间复杂度为 $O(h)$（$h$ 为树高）。这正是中序遍历在"按序处理节点"场景下的典型应用，说明掌握本题的遍历模板可以直接迁移到更多进阶题目。

6. 与前后序遍历的横向对比

将本题解与仓库中的 0144. 二叉树的前序遍历题解 对照阅读，可以清晰看到三种深度优先遍历的异同：

三种遍历的递归与迭代时间复杂度均为 $O(n)$；非递归实现中，中序的关键约束是"左子树访问前当前节点不能提前出栈"，这是与前序（出栈即访问）最本质的区别。

7. 仓库延伸阅读

本专题在 AlgoNote 仓库中有着完整的知识链路，建议按以下顺序深入学习：

• 二叉树的中序遍历题解（本文主体）：递归与显式栈双解法原文；
• 二叉树的遍历教程：前序、中序、后序、层序四种遍历的系统讲解与对比总结表；
• 二叉树的前序遍历题解：对照阅读，理解三种 DFS 遍历的入栈差异；
• 二叉搜索树中第 K 小的元素题解：中序遍历在 BST 上的实战应用；
• 二叉搜索树基础教程：理解中序遍历输出有序序列的数学基础；
• 算法题目分类列表：二叉树的遍历题目清单，可继续刷题巩固。

通过本题，建议同时掌握「递归模板 + 显式栈模拟系统栈」两种能力，前者保证面试正确率，后者应对高难度工程化约束，二者结合即可从容应对二叉树遍历的一切变体题目。

• 教程
• 文档
• 知识库