本文深入剖析二叉树中序遍历（inorder traversal）的递归执行机制，通过调用栈演化、节点访问顺序和完整示例图解，清晰揭示“左→根→右”遍历逻辑如何在递归调用中层层展开与回溯。
中序遍历的核心规则是：对任意节点，先递归遍历其左子树，再访问该节点自身，最后递归遍历其右子树。这种“左–根–右”的顺序保证了——当二叉树为二叉搜索树（BST）时，遍历结果天然升序排列。而递归的精妙之处，在于它将这一全局规则自动分解并应用于每一层子树。
以下代码是标准的中序遍历递归实现：
class Solution {
public List inorderTraversal(TreeNode root) {
List result = new ArrayList<>();
inorderHelper(root, result);
return result;
}
private void inorderHelper(TreeNode node, List result) {
if (node == null) return; // 递归终止条件：空节点直接返回
inorderHelper(node.left, result); // ① 递归进入左子树
result.add(node.val); // ② 访问当前节点（收集值）
inorderHelper(node.right, result); // ③ 递归进入右子树
}
} ? 执行过程可视化（以如下树为例）
5
/ \
3 7
/ \ / \
1 4 6 8
\ \
2 9我们从 inorderHelper(5, result) 开始，逐步追踪调用栈变化：
| 步骤 | 当前节点 | 动作 | result 状态 | 调用栈（栈顶→栈底） |
|---|---|---|---|---|
| 1 | 5 | 进入左 → 调用 inorderHelper(3, ...) | [] | [5] |
| 2 | 3 | 进入左 → 调用 inorderHelper(1, ...) | [] | [5, 3] |
| 3 | 1 | 进入左 → null，返回 | [] | [5, 3, 1] |
| 4 | 1 | 执行 add(1) | [1] | [5, 3, 1] |
| 5 | 1 | 进入右 → 调用 inorderHelper(2, ...) | [1] | [5, 3, 1, 2] |
| 6 | 2 | 左=null → add(2) → 右=null → 返回 | [1, 2] | [5, 3, 1, 2] |
| 7 | 1 | inorderHelper(2) 返回，1 的递归结束 → 返回上层 | [1, 2] | [5, 3, 1] |
| 8 | 3 | 执行 add(3) | [1, 2, 3] | [5, 3] |
| 9 | 3 | 进入右 → inorderHelper(4, ...) → add(4) → 返回 | [1, 2, 3, 4] | [5, 3] |
| 10 | 3 | 返回 → 回到 5 层 | [1, 2, 3, 4] | [5] |
| 11 | 5 | 执行 add(5) | [1, 2, 3, 4, 5] | [5] |
| 12 | 5 | 进入右 → 同理遍历 7→6→8→9 子树 | [1,2,3,4,5,6,7,8,9] | [5] |
✅ 最终输出：[1, 2, 3, 4, 5, 6, 7, 8, 9] —— 完美体现 BST 的有序性。
⚠️ 关键注意事项
- 递归必须有明确的 base case：if (node == null) return; 是防止无限递归和空指针异常的生命线。
-
访问时机决定遍历类型：
- add() 在两次递归之间 → 中序（Left–Root–Right）
- add() 在第一次递归前 → 前序（Root–Left–Right）
- add() 在两次递归后 → 后序（Left–Right–Root）
- 空间复杂度由递归深度决定：最坏情况（链状树）为 O(n)，平均为 O(log n)；时间复杂度恒为 O(n)，因每个节点访问且仅访问一次。
- 避免在递归方法中新建列表：如原代码中在 inorderTraversal() 内创建 ArrayList 并传入辅助方法，可避免重复对象创建，提升效率与内存局部性。
掌握递归遍历，本质是理解「函数调用栈」如何自然模拟树的深度优先探索路径。动手在纸上画出调用栈+节点访问序列，是突破理解瓶颈最有效的方法。
