LeetCode 94. 二叉树的中序遍历 详细技术解析

LeetCode 94. 二叉树的中序遍历 详细技术解析专栏推荐LeetCode 算法实战 | 二叉树专项突破标签LeetCode、二叉树、中序遍历、递归、迭代、Python、数据结构文章目录一、题目解析题干示例提示进阶要求二、核心知识点二叉树中序遍历定义三、解题思路递归迭代满足进阶要求四、代码实现Python版贴合指定格式含详细注释五、代码优化与复杂度分析六、常见易错点与避坑指南七、相似题目拓展二叉树遍历专项八、总结本文针对 LeetCode 94. 二叉树的中序遍历 一题进行全面的技术解析。从题目理解、核心知识点铺垫到递归/迭代两种思路推导、代码实现严格贴合题目指定格式再到优化升级、易错点总结全程贴合算法实战场景兼顾新手入门和进阶巩固代码可直接复制提交附带详细注释便于理解同时满足题目“迭代算法实现”的进阶要求。一、题目解析题干示例提示进阶要求1.1 题干核心信息给定一个二叉树的根节点root返回它的中序遍历结果以列表形式返回节点值。补充说明二叉树节点结构已给定题干指定格式无需自行定义只需实现inorderTraversal方法接收根节点root返回遍历后的节点值列表。1.2 示例解析示例 1输入root [1,null,2,3] → 输出[1,3,2]解析二叉树结构如下层序表示1根节点└── 右子树2└── 左子树3中序遍历顺序左子树 → 根节点 → 右子树即 1 的左子树空→ 1 → 2 的左子树3→ 2 → 2 的右子树空最终结果 [1,3,2]。示例 2输入root [] → 输出[]解析空树无节点中序遍历结果为空列表。示例 3输入root [1] → 输出[1]解析只有根节点中序遍历顺序为 根节点无左、右子树结果为 [1]。1.3 题目提示关键约束树中节点数目范围0 ≤ 节点数 ≤ 100数据量小两种算法均能高效运行无需考虑极端性能问题节点值范围-100 ≤ Node.val ≤ 100无需处理异常值直接存储节点值即可输入的二叉树以层序遍历形式给出如 [1,null,2,3]null 表示对应位置无节点。1.4 进阶要求题干明确要求递归算法很简单需通过迭代算法完成。因此本文将重点实现两种算法重点讲解迭代算法的思路递归作为基础快速实现迭代作为进阶突破难点。二、核心知识点二叉树中序遍历定义中序遍历In-order Traversal是二叉树三大遍历方式前序、中序、后序之一核心遍历顺序为左子树 → 根节点 → 右子树递归执行直到所有节点遍历完毕关键特点递归特性对每个节点均先遍历其左子树再访问节点本身最后遍历其右子树空树处理若当前节点为空null则无需遍历直接返回应用场景常用于二叉搜索树BST中序遍历结果为升序排列本题虽不是BST但遍历逻辑通用。三、解题思路递归迭代满足进阶要求3.1 思路1递归算法基础简单易实现核心逻辑贴合中序遍历定义终止条件若当前节点root为空直接返回空列表递归遍历左子树调用自身传入左子节点root.left获取左子树的中序遍历结果访问当前节点将当前节点的值root.val加入结果列表递归遍历右子树调用自身传入右子节点root.right获取右子树的中序遍历结果返回结果左子树遍历结果 当前节点值 右子树遍历结果拼接为最终列表。优势代码极简逻辑清晰无需额外数据结构劣势递归深度取决于树的高度若树为斜树如所有节点只有左子树递归深度可达100节点数上限但题目节点数≤100不会出现栈溢出可安全使用。3.2 思路2迭代算法进阶满足题干要求核心逻辑用栈模拟递归的调用过程递归本质是系统栈实现迭代需手动维护栈核心步骤如下初始化创建一个空栈stack用于存储待遍历的节点创建一个空列表res用于存储遍历结果定义当前节点cur root循环条件栈不为空或当前节点cur不为空左子树遍历将当前节点cur及其所有左子节点依次压入栈直到cur为空对应递归中“遍历左子树”的过程访问节点弹出栈顶节点将其值加入res对应递归中“访问当前节点”右子树遍历将当前节点cur设为弹出节点的右子节点对应递归中“遍历右子树”的过程重复步骤2-5直到栈为空且cur为空遍历结束返回res。关键理解栈的作用是“暂存”未访问的节点先压入左子节点确保左子树先遍历再访问根节点最后处理右子树完全贴合中序遍历顺序。四、代码实现Python版贴合指定格式含详细注释严格按照题干指定的代码格式编写分别实现递归版和迭代版重点实现迭代版满足进阶要求代码可直接复制到LeetCode提交无语法错误。4.1 递归版代码基础版简单易写递归版代码可直接提交# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def inorderTraversal(self, root: Optional[TreeNode]) - List[int]: 二叉树中序遍历递归版 :param root: 二叉树的根节点 :return: 中序遍历的节点值列表 # 终止条件当前节点为空返回空列表 if not root: return [] # 递归逻辑左子树遍历 当前节点值 右子树遍历 return self.inorderTraversal(root.left) [root.val] self.inorderTraversal(root.right)4.2 迭代版代码进阶版满足题干要求迭代版代码重点可直接提交# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def inorderTraversal(self, root: Optional[TreeNode]) - List[int]: 二叉树中序遍历迭代版满足进阶要求 :param root: 二叉树的根节点 :return: 中序遍历的节点值列表 # 初始化栈存储待遍历节点和结果列表 stack [] res [] # 当前节点从根节点开始 cur root # 循环条件栈不为空 或 当前节点不为空避免漏遍历右子树 while stack or cur: # 1. 遍历当前节点的所有左子节点依次压入栈 while cur: stack.append(cur) cur cur.left # 移动到左子节点直到左子节点为空 # 2. 弹出栈顶节点此时左子树已遍历完毕访问该节点 node stack.pop() res.append(node.val) # 3. 遍历当前节点的右子树重复上述流程 cur node.right # 返回最终遍历结果 return res补充迭代版优化Morris遍历空间复杂度O(1)进阶优化上述迭代版空间复杂度为O(n)栈最多存储n个节点Morris遍历可实现空间复杂度O(1)无需栈利用二叉树的空闲指针适合追求极致空间效率的场景代码如下Morris遍历版优化空间# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def inorderTraversal(self, root: Optional[TreeNode]) - List[int]: res [] cur root # Morris遍历核心找到当前节点左子树的最右节点建立线索 while cur: # 情况1当前节点无左子树直接访问然后去右子树 if not cur.left: res.append(cur.val) cur cur.right else: # 情况2有左子树找到左子树最右节点前驱节点 predecessor cur.left while predecessor.right and predecessor.right ! cur: predecessor predecessor.right # 子情况2.1前驱节点右指针为空建立线索指向当前节点 if not predecessor.right: predecessor.right cur cur cur.left # 继续遍历左子树 # 子情况2.2前驱节点右指针指向当前节点说明左子树已遍历访问当前节点 else: predecessor.right None # 取消线索恢复树结构 res.append(cur.val) cur cur.right # 去右子树 return res五、代码优化与复杂度分析5.1 三种算法复杂度对比算法类型时间复杂度空间复杂度优势劣势递归版O(n)O(h)h为树的高度代码极简逻辑清晰递归深度过大可能栈溢出本题无影响栈迭代版O(n)O(n)最坏情况斜树无递归栈溢出风险易理解需额外维护栈空间开销较大Morris遍历版O(n)O(1)空间效率最优无栈开销逻辑复杂需修改树结构临时线索说明n为二叉树节点总数所有算法均需遍历每个节点一次时间复杂度均为O(n)h为树的高度递归版空间复杂度为系统递归栈的深度平衡树hlogn斜树hn。5.2 优化建议实战选型面试/日常练习优先写栈迭代版既满足题干进阶要求又易理解、无栈溢出风险追求空间效率使用Morris遍历版适合面试官追问“如何优化空间复杂度”快速提交/简单场景使用递归版代码极简节省编写时间。六、常见易错点与避坑指南易错点1迭代版栈循环条件错误错误仅判断“栈不为空”忽略“当前节点cur不为空”导致右子树漏遍历如示例1中节点2的右子树虽为空但cur需指向2的右子树触发栈弹出避坑循环条件必须是while stack or cur两者满足其一即可进入循环。易错点2递归版终止条件遗漏错误未判断if not root直接递归调用导致空节点报错如输入root为空时无法访问root.left避坑递归函数开头必须添加终止条件空节点返回空列表。易错点3迭代版节点压栈顺序错误错误先压入节点再判断左子树导致节点重复压栈或漏压左子节点避坑内层循环需“先判断cur不为空再压栈再移动cur到左子节点”确保所有左子节点都被压入栈。易错点4Morris遍历线索未取消错误建立前驱节点的右指针线索后未在访问节点后取消导致树结构被破坏避坑在子情况2.2中访问当前节点后必须将前驱节点的right设为None恢复原树结构。易错点5节点值存储顺序错误错误混淆中序遍历顺序如先访问根节点再遍历左子树导致结果错误避坑牢记“左→根→右”递归版中先递归左子树再添加当前节点值迭代版中先压左子树弹出栈顶节点后再添加值。七、相似题目拓展二叉树遍历专项通过以下相似题目巩固二叉树三大遍历方式形成专项突破LeetCode 144. 二叉树的前序遍历遍历顺序根→左→右递归/迭代实现LeetCode 145. 二叉树的后序遍历遍历顺序左→右→根难度稍高迭代实现需注意节点访问时机LeetCode 102. 二叉树的层序遍历广度优先遍历用队列实现与深度优先遍历对比练习LeetCode 98. 验证二叉搜索树利用中序遍历升序特性进阶应用。八、总结本题是二叉树遍历的基础经典题核心考察中序遍历的定义和递归/迭代两种实现方式重点突破迭代算法满足题干进阶要求。核心收获掌握中序遍历“左→根→右”的核心顺序理解递归与迭代的本质区别递归靠系统栈迭代靠手动栈迭代算法的关键是用栈“暂存”未访问的节点先处理左子树再访问根节点最后处理右子树Morris遍历是空间优化的进阶方案适合追求极致空间效率的场景需掌握“线索树”的构建与恢复避开常见易错点如循环条件、终止条件、节点压栈顺序提升代码健壮性。本题是二叉树专项的入门题掌握两种实现方式后可快速迁移到前序、后序遍历题目中为后续复杂二叉树问题如路径总和、二叉树重构打下基础。