94. 二叉树的中序遍历 (Easy)
专题归类： 05-二叉树 LeetCode 链接： https://leetcode.cn/problems/binary-tree-inorder-traversal/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给定一个二叉树的根节点 root，返回它的 中序 遍历。
中序遍历 的定义：按照 左子树 → 根节点 → 右子树 的顺序访问二叉树中的所有节点。
示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
提示：
- 树中节点数目范围在
[0, 100]内 -100 <= Node.val <= 100
进阶： 递归解法很简单，你能否用迭代方式完成？
题目详细分析
- 数据范围含义： 节点数最多 100，值范围 [-100, 100]，非常小，任何合法解法都不会超时。递归深度最多 100，不会栈溢出。
- 输入输出特征： 输入是树的根节点，输出是节点值列表（按中序顺序）。
- 边界条件： 空树（root 为 None）返回空列表
[]；只有一个节点直接返回该节点值。 - 核心约束： 必须按照左→根→右的顺序严格访问。
- 隐藏条件： 进阶要求是掌握非递归（迭代）写法，面试中常考。
小白版直白理解
就像你在一个图书馆里整理书籍，你的规则是：先看完左边书架的所有书，再看中间展台上的书，最后看右边书架的书。中序遍历就是对着二叉树执行这个规则——先走完左子树的全部节点，然后访问当前节点，最后走完右子树的全部节点。
解题思路
思路一：递归法（推荐）
中序遍历的递归写法是最直观的。利用函数调用栈天然地实现「先深入左子树 → 回到根 → 再深入右子树」的过程。
为什么选这个遍历顺序？ 中序就是「左→根→右」，递归的天然结构完美匹配这个顺序：先递归左子树，再访问当前节点，最后递归右子树。
def inorderTraversal(root):
res = []
def dfs(node):
if not node:
return
dfs(node.left) # 左：递归遍历左子树
res.append(node.val) # 根：访问当前节点（中序位置）
dfs(node.right) # 右：递归遍历右子树
dfs(root)
return res思路二：迭代法（栈模拟）
用栈手动模拟递归过程。核心思想是：一路向左将所有左子节点入栈，当无法再向左时，弹出栈顶访问它，然后转向右子树继续。
优点： 不使用系统递归栈，能更好地控制遍历流程，且可以提前终止遍历。
def inorderTraversal(root):
res, stack = [], []
cur = root
while cur or stack:
# 一路向左，将路径上的节点全部入栈
while cur:
stack.append(cur)
cur = cur.left
# 弹出栈顶（最左节点），访问它
cur = stack.pop()
res.append(cur.val)
# 转向右子树
cur = cur.right
return res思路三：Morris 遍历（进阶）
利用叶子节点的空指针（空闲指针）建立临时线索，实现 O(1) 额外空间 的遍历。核心思想是：将当前节点的前驱节点（左子树最右节点）的 right 指针指向当前节点，从而在遍历完左子树后能回到当前节点。
适用场景： 面试中展示对遍历的深层理解，或空间受限的环境。
def inorderTraversal(root):
res = []
cur = root
while cur:
if not cur.left:
# 没有左子树，访问当前节点，进入右子树
res.append(cur.val)
cur = cur.right
else:
# 找左子树的最右节点（前驱）
pre = cur.left
while pre.right and pre.right != cur:
pre = pre.right
if not pre.right:
# 建立线索
pre.right = cur
cur = cur.left
else:
# 恢复树结构
pre.right = None
res.append(cur.val)
cur = cur.right
return res易错点
- 忘记 base case： 递归函数中必须先处理
if not node: return，否则会无限递归导致栈溢出。 - 迭代法忘记转向右子树： 弹出访问完节点后，必须将 cur 指向 cur.right，否则会死循环。
- Morris 遍历修改了树： 虽然最后会恢复，但如果在遍历过程中读取树结构会有问题（多线程环境不安全）。
- 将结果放入的位置搞错： 中序是在递归完左子树后、递归右子树前访问节点，放入 res。
框架提炼
递归遍历二叉树模板（中序）：
def traverse(node):
if not node:
return
traverse(node.left) # 左
# 访问当前节点 # 根（中序位置）
traverse(node.right) # 右通用套路： 所有二叉树递归问题都可以归结为「在哪个位置做什么事」——前序位置（刚进入节点）、中序位置（左子树回来后）、后序位置（右子树回来后）。中序位置的特点是：处理完左子树全部信息后回来，此时可以拿到左子树的结果，但还没有碰右子树。
关联题目
- 98-验证二叉搜索树 — 利用 BST 中序遍历结果严格递增的特性来验证合法性。
- 230-BST第K小的元素 — 中序遍历 BST 得到递增序列，第 k 个访问到的节点即为第 k 小元素。
- 102-二叉树的层序遍历 — 对比 BFS 和 DFS（中序作为 DFS 的一种）的遍历思维差异。