本文通过图解与分步调用追踪，清晰阐释中序遍历递归代码的执行流程，结合示例树结构逐层展开函数调用栈、访问顺序与结果生成逻辑，帮助读者真正掌握“左→根→右”递归本质。
二叉树的中序遍历（Inorder Traversal）遵循 “左子树 → 当前节点 → 右子树” 的访问顺序。其递归实现简洁而精妙，但初学者常因难以可视化调用栈而困惑。下面我们将以经典递归代码为基础，结合具体树例，逐帧解析其执行过程。
? 示例树结构
考虑如下二叉树（满足BST性质，便于验证排序结果）：
5
/ \
3 7
/ \ / \
1 4 6 8
\ \
2 9? 递归执行逻辑分解
核心方法 result(TreeNode root, ArrayList
- 递归进入左子树：result(root.left, inorder)
- 访问当前节点：inorder.add(root.val)
- 递归进入右子树：result(root.right, inorder)
✅ 关键理解：每次调用 result 都代表“处理以 root 为根的子树”，而空节点（root == null）是递归终止条件（base case），直接返回，不执行后续操作。
? 分步调用追踪（精简版）
从 result(5, ...) 开始，我们用缩进表示调用层级，→ 表示执行流向：
result(5) ├─ result(3) // 进入左子树 │ ├─ result(1) // 进入左子树 │ │ ├─ result(null) → return // 左空，回退 │ │ ├─ add(1) // 访问节点1 │ │ └─ result(2) // 进入右子树 │ │ ├─ result(null) → return │ │ ├─ add(2) // 访问节点2 │ │ └─ result(null) → return │ ├─ add(3) // 回到节点3，访问自身 │ └─ result(4) // 进入右子树 │ ├─ result(null) → return │ ├─ add(4) │ └─ result(null) → return ├─ add(5) // 回到根节点5，访问自身 └─ result(7) // 进入右子树（同理展开：6 → 7 → 8 → 9）
最终 inorder 列表为：[1, 2, 3, 4, 5, 6, 7, 8, 9] —— 完全有序，印证了中序遍历在BST中生成升序序列的特性。
? 重要注意事项
- 调用栈是隐式“记忆体”：每次递归调用都会在栈中保存当前 root 和局部执行位置（即下一步该执行 add 还是 right 调用），返回时自动恢复上下文。
- 访问时机不可错位：add(root.val) 必须位于两次递归调用之间——这是实现“左→根→右”的唯一方式；若前置则成前序，后置则成后序。
- 空间复杂度由深度决定：最坏情况（链状树）递归深度为 O(n)，栈空间开销为 O(n)；平均情况（平衡树）为 O(log n)。
- 避免副作用陷阱：本实现将 ArrayList 作为参数传递（引用传递），确保所有递归层级操作同一列表对象；若在每层新建列表并拼接，则时间复杂度升至 O(n²)。
✅ 总结
中序递归不是“魔法”，而是对树结构的自然映射：每个节点都承诺——先让左孩子完成全部工作，再轮到自己，最后托付右孩子继续相同承诺。手动画出调用栈 + 小规模树例演练，是突破理解瓶颈最有效的方法。掌握此模式，前序、后序乃至更复杂的树形DP都将水到渠成。
