请解释二叉树中序遍历递归代码的执行逻辑

先明确中序遍历的核心规则：按照「左子树 → 根节点 → 右子树」的顺序遍历节点，递归的本质就是把这个规则套用到每一棵子树上。

代码结构拆解 #

你提供的代码分为两部分：

1. inorderTraversal方法：初始化存储结果的ArrayList，调用递归方法result后返回结果列表。
2. result方法：真正实现递归遍历的核心逻辑，包含三个关键步骤：
   • 终止条件：如果当前节点root为null，直接返回（这是递归的“出口”，避免无限调用）。
   • 递归遍历左子树：调用result(root.left, inorder)。
   • 记录当前节点值：将root.val加入结果列表。
   • 递归遍历右子树：调用result(root.right, inorder)。

用具体树结构模拟递归执行过程 #

我们用一棵典型的二叉树来一步步走流程，树结构如下：

5
   / \
  3   7
 / \ / \
1  4 6  8

执行步骤：

1. 初始调用result(5, list)：
   • 5不为null，先执行result(3, list)，当前方法暂停，等待这个调用返回。
2. 进入result(3, list)：
   • 3不为null，执行result(1, list)，当前方法暂停。
3. 进入result(1, list)：
   • 1不为null，执行result(1.left, list)（1的左子节点是null），这个调用触发终止条件，直接返回。
   • 回到result(1, list)，继续执行inorder.add(1)，此时列表为[1]。
   • 执行result(1.right, list)（1的右子节点是null），调用返回。
   • result(1, list)执行完毕，回到result(3, list)。
4. 回到result(3, list)，执行inorder.add(3)，列表变为[1, 3]。
   • 执行result(4, list)，当前方法暂停。
5. 进入result(4, list)：
   • 4不为null，执行result(4.left, list)（null），返回。
   • 执行inorder.add(4)，列表变为[1, 3, 4]。
   • 执行result(4.right, list)（null），返回。
   • result(4, list)执行完毕，回到result(5, list)。
6. 回到result(5, list)，执行inorder.add(5)，列表变为[1, 3, 4, 5]。
   • 执行result(7, list)，当前方法暂停。
7. 进入result(7, list)：
   • 7不为null，执行result(6, list)，当前方法暂停。
8. 进入result(6, list)：
   • 6不为null，执行result(6.left, list)（null），返回。
   • 执行inorder.add(6)，列表变为[1, 3, 4, 5, 6]。
   • 执行result(6.right, list)（null），返回。
   • result(6, list)执行完毕，回到result(7, list)。
9. 回到result(7, list)，执行inorder.add(7)，列表变为[1, 3, 4, 5, 6, 7]。
   • 执行result(8, list)，当前方法暂停。
10. 进入result(8, list)：
    • 8不为null，执行result(8.left, list)（null），返回。
    • 执行inorder.add(8)，列表变为[1, 3, 4, 5, 6, 7, 8]。
    • 执行result(8.right, list)（null），返回。
    • result(8, list)执行完毕，回到result(7, list)，再回到result(5, list)，所有递归调用执行完毕。

关键细节说明 #

• 递归栈的作用：每一次调用result方法，JVM都会在栈中创建一个新的方法帧，保存当前的root参数和代码执行位置。当某个调用触发终止条件返回时，栈顶的方法帧会恢复执行，继续处理后续的添加节点和右子树遍历。
• 引用传递的列表：ArrayList是引用类型，所有递归调用操作的都是同一个列表对象，不会生成多个独立列表，最终所有节点值都会按顺序存入这个列表。

内容的提问来源于stack exchange，提问作者Vishnu Vardhan