LeetCode 0094 二叉树的中序遍历：递归与显式栈迭代双解法详解（AlgoNote 算法通关手册）

教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本篇技术指南围绕「算法通关手册」AlgoNote 仓库中的经典题解 0094. 二叉树的中序遍历 展开系统讲解二叉树中序遍历的「左子树 → 根节点 → 右子树」访问规则并给出递归与显式栈迭代两种完整可运行的 Python 实现。读完本文你将掌握中序遍历的递归模板、非递归模拟系统栈的关键技巧理解其在二叉搜索树BST有序序列生成、求第 K 小元素等高频场景中的应用并能与同仓库的前序、后序遍历解法横向对比。1. 题目理解LeetCode 0094 要求什么1.1 题目大意给定一个二叉树的根节点root要求返回该二叉树的中序遍历结果。中序遍历遵循「左子树 → 根节点 → 右子树」的访问顺序先递归遍历左子树再访问当前根节点最后递归遍历右子树。只要严格遵循这一顺序无论子树多深最终输出的节点值序列都是中序序列。1.2 数据范围与约束约束项取值范围树中节点数目$[0, 100]$可以为空树节点值Node.val$[-100, 100]$空树root []属于合法输入返回值应为空列表[]。1.3 示例示例 1输入root [1,null,2,3] 输出[1,3,2]该树结构为根节点1右子树根节点22的左孩子为3。按中序顺序遍历得到1 → 3 → 2。示例 2输入root [] 输出[]2. 解题思路 1递归遍历2.1 算法思想二叉树本身具有递归结构根节点 左子树 右子树因此中序遍历可以自然地用递归实现。递归实现步骤为判断二叉树是否为空为空则直接返回递归终止条件。先递归遍历左子树。然后访问根节点将root.val加入结果列表。最后递归遍历右子树。关键在于访问根节点这一操作的位置它被放在左子树递归调用之后、右子树递归调用之前这正是中序遍历区别于前序根在最前与后序根在最后的本质所在。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手动模拟整个递归过程从而避免递归深度过大带来的栈溢出风险。核心难点与前序遍历不同中序遍历要求访问根节点必须发生在左子树全部遍历完之后。因此必须保证——在左子树访问完成之前当前节点不能提前出栈。具体做法判断二叉树是否为空为空则直接返回。初始化一个空栈stack。当根节点或栈不为空时循环执行若当前节点不为空循环遍历左子树不断将当前子树的根节点入栈直到到达最左侧节点若当前节点为空说明已无左子树此时弹出栈顶元素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 res3.3 复杂度分析时间复杂度$O(n)$。每个节点入栈一次、出栈一次总操作次数与节点数 $n$ 线性相关。空间复杂度$O(n)$。栈中最多同时存放树的高度 $h$ 个节点最坏情况链状树为 $O(n)$。4. 两种思路对比与选型建议对比维度递归实现显式栈迭代实现代码量极短结构直观稍长需理解入栈/出栈时机依赖依赖系统调用栈手动维护显式栈栈溢出风险树深较大时存在可规避由显式栈控制时空复杂度均为 $O(n)$均为 $O(n)$适用场景面试快速作答、逻辑演示生产环境大深度树、工程化要求两者的时间与空间复杂度完全一致。选型建议笔试/面试优先写递归代码简洁不易出错若题目明确要求非递归或树深度可能超过递归栈限制如 $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. 二叉树的前序遍历题解 对照阅读可以清晰看到三种深度优先遍历的异同遍历方式访问顺序递归实现关键差异非递归实现关键差异前序遍历根 → 左 → 右先res.append再递归根先入栈右子树先入栈、左子树后入栈保证左先弹出中序遍历本题左 → 根 → 右递归左子树后再res.append一路向左入栈无左子树时弹出并访问再转向右子树后序遍历左 → 右 → 根左右子树递归完后再res.append需额外标记右子树访问状态如prev指针三种遍历的递归与迭代时间复杂度均为 $O(n)$非递归实现中中序的关键约束是左子树访问前当前节点不能提前出栈这是与前序出栈即访问最本质的区别。7. 仓库延伸阅读本专题在 AlgoNote 仓库中有着完整的知识链路建议按以下顺序深入学习二叉树的中序遍历题解本文主体递归与显式栈双解法原文二叉树的遍历教程前序、中序、后序、层序四种遍历的系统讲解与对比总结表二叉树的前序遍历题解对照阅读理解三种 DFS 遍历的入栈差异二叉搜索树中第 K 小的元素题解中序遍历在 BST 上的实战应用二叉搜索树基础教程理解中序遍历输出有序序列的数学基础算法题目分类列表二叉树的遍历题目清单可继续刷题巩固。通过本题建议同时掌握「递归模板 显式栈模拟系统栈」两种能力前者保证面试正确率后者应对高难度工程化约束二者结合即可从容应对二叉树遍历的一切变体题目。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐二叉树前序遍历全解递归 DFS、迭代栈与 Morris 遍历LeetCode 144二叉树前序遍历全解递归 DFS、迭代栈与 Morris 遍历LeetCode 144 本文以 LeetCode 144「二叉树的前序遍历」为核心系统讲解示例工程教程algorithm-base 二叉树中序遍历 Morris 算法详解从递归、迭代到 O(1) 空间遍历algorithm base 二叉树中序遍历 Morris 算法详解从递归、迭代到 O 1 空间遍历 导读 本篇基于 algorithm base 仓库 二叉文档教程知识库二叉树遍历全攻略AlgoNote 中前序、中序、后序与层序遍历的递归与显式栈实现二叉树遍历全攻略AlgoNote 中前序、中序、后序与层序遍历的递归与显式栈实现 导读 本文以 AlgoNote https://link.gitcode.教程文档知识库上一篇Rax移动端图片优化加载速度与内存占用优化方案下一篇7个实用技巧掌握fastai早停法从验证损失监控到最佳模型保存全攻略创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考