请解析二叉树中序遍历递归函数的执行流程及打印逻辑

Hey，我来给你把这个中序遍历递归函数的执行流程拆解得明明白白，用例子说话，保证你能get到每一步～

一、先看函数核心框架 #

先把你给出的代码贴出来方便对照：

public void InOrder(Node node) {
    if (node != null) {
        InOrder(node.left);
        System.out.print(" " + node.key);
        InOrder(node.right);
    }
}

这个函数的核心逻辑就是严格遵循左子树 → 当前节点 → 右子树的中序遍历规则，递归是它实现这个规则的关键。

二、用具体二叉树例子走一遍完整流程 #

我们拿一个最简单的二叉树来模拟执行，树的结构如下：

2
   / \
  1   3

假设每个Node对象有key（节点值）、left（左子节点）、right（右子节点）三个属性。现在从根节点（值为2的节点）开始调用InOrder(root)，一步步看：

1. 第一次调用InOrder(2)：节点不为空，先执行InOrder(node.left)，也就是调用InOrder(1)。
2. 进入InOrder(1)：节点不为空，执行InOrder(node.left)——节点1的左子节点是null，所以这个递归调用直接返回（啥都不做）。
3. 回到InOrder(1)的逻辑：左子树遍历完了，执行System.out.print(" " + 1)，控制台输出「 1」。
4. 接着执行InOrder(node.right)——节点1的右子节点是null，这个递归调用直接返回。
5. 现在InOrder(1)的所有步骤都完成了，回到最初的InOrder(2)：左子树遍历完成，执行System.out.print(" " + 2)，控制台输出「 2」（现在整体输出是「 1 2」）。
6. 然后执行InOrder(node.right)，也就是调用InOrder(3)。
7. 进入InOrder(3)：节点不为空，执行InOrder(node.left)——节点3的左子节点是null，直接返回。
8. 回到InOrder(3)的逻辑：执行System.out.print(" " + 3)，控制台输出「 3」（整体输出变成「 1 2 3」）。
9. 执行InOrder(node.right)——节点3的右子节点是null，直接返回。
10. InOrder(3)执行完成，回到InOrder(2)，所有步骤都走完，整个函数执行结束。

三、函数的返回时机拆解 #

递归函数的返回其实分两种场景：

• 直接返回：当传入的node是null时，if (node != null)条件不成立，函数直接返回，不会执行任何内部的递归或打印逻辑。
• 完成所有逻辑后返回：当某个节点对应的「左子树递归遍历 → 当前节点打印 → 右子树递归遍历」这三步全部执行完成后，这个节点的InOrder调用才会返回，回到上一层调用的逻辑中继续执行。

比如上面例子里，InOrder(1)的返回是在它的左空节点返回、打印1、右空节点返回之后，才回到InOrder(2)的下一步（打印2）。

四、左、当前、右节点的打印逻辑本质 #

这个逻辑就是中序遍历的灵魂：左子树的所有节点必须在当前节点之前被打印，右子树的所有节点必须在当前节点之后被打印。

• 左节点处理：递归不断深入左子树，直到碰到空节点才回溯，回溯时会从最底层的左子节点开始，按照「左-根-右」的顺序打印左子树的所有节点。
• 当前节点打印：只有当它的左子树完全遍历完毕（包括左子树内部的所有节点都处理完），才会触发当前节点的打印操作。
• 右节点处理：当前节点打印完成后，才会开始递归处理右子树，右子树内部同样遵循「左-根-右」的顺序完成打印。

说白了，递归就是把每个节点的处理逻辑复制了一遍——每个节点都要先搞定自己的左孩子全家，再自己出场，最后搞定右孩子全家。

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