LeetCode 94：二叉树的中序遍历（Binary Tree Inorder Traversal）题解

Binary Tree Inorder Traversal 是 LeetCode Hot 100 里面一道非常经典的二叉树基础题。

这道题看起来不难，甚至很多人第一次刷二叉树题时，都会把它当成“送分题”。 因为题目要求的事情很直接：

按照中序遍历的顺序，把二叉树节点的值依次输出出来。

但这道题之所以重要，并不是因为它难，而是因为它几乎是学习二叉树递归遍历时最基础、最标准的一道模板题。

你给出的这份 Java 代码，使用的是这道题最经典的一种做法：

递归遍历

并且它把中序遍历最核心的顺序完整体现了出来：

左子树 -> 根节点 -> 右子树

本文就结合这段代码，系统地讲一下这道题的思路。

题目介绍

给定一个二叉树的根节点 root，要求你返回它的 中序遍历 结果。

所谓中序遍历，访问顺序是：

左子树 -> 根节点 -> 右子树

也就是说，对于任意一个节点：

1. 先遍历它的左孩子

2. 再访问它自己

3. 最后遍历它的右孩子

例如下面这棵树：

    1
     \
      2
     /
    3

它的中序遍历顺序就是：

[1,3,2]

因为：

• 节点 1 没有左子树，所以先访问 1

• 然后进入右子树 2

• 在访问 2 之前，先访问它的左子树 3

• 最后再访问 2

示例

示例 1

输入：root = [1,null,2,3]
输出：[1,3,2]

对应二叉树结构为：

    1
     \
      2
     /
    3

中序遍历顺序：

• 先访问 1

• 再访问 3

• 最后访问 2

所以结果是：

[1,3,2]

示例 2

输入：root = []
输出：[]

空树没有任何节点，所以结果是空列表。

示例 3

输入：root = [1]
输出：[1]

只有一个节点时，中序遍历结果就是它自己。

什么是中序遍历？

二叉树遍历最经典的三种递归遍历方式分别是：

• 前序遍历：根 -> 左 -> 右

• 中序遍历：左 -> 根 -> 右

• 后序遍历：左 -> 右 -> 根

这道题考察的就是第二种：

左 -> 根 -> 右

也就是说，当你站在一个节点上时，应该按这样的顺序处理：

1. 递归遍历左子树

2. 访问当前节点

3. 递归遍历右子树

这三个步骤只要顺序不变，就是中序遍历。

为什么这道题适合用递归？

因为二叉树本身就是一种递归结构。

对于一棵树来说：

• 它的左子树本身也是一棵树

• 它的右子树本身也是一棵树

而中序遍历的定义又恰好是：

• 先中序遍历左子树

• 再访问根节点

• 再中序遍历右子树

你会发现，“树的定义”和“遍历的定义”都天然适合递归。 所以这类题最自然的做法就是递归。

也正因为如此，这道题常常被当成学习树递归的第一批模板题。

Java 代码

下面是你给出的代码，我这里保留原始逻辑，并加上注释：

class Solution {
    List<Integer> res = new ArrayList<>();

    public List<Integer> inorderTraversal(TreeNode root) {
        if (root != null) traversal(root);
        return res;
    }

    public void read(TreeNode node) {
        res.add(node.val);
    }

    public void traversal(TreeNode node) {
        // 先遍历左子树
        if (node.left != null) traversal(node.left);

        // 再访问当前节点
        read(node);

        // 最后遍历右子树
        if (node.right != null) traversal(node.right);
    }
}

代码拆解

这段代码整体非常清晰，而且把“中序遍历”的顺序写得很直接。 下面一步一步来看。

1. res 是做什么的？

List<Integer> res = new ArrayList<>();

这是结果列表，用来保存中序遍历过程中访问到的节点值。

每访问到一个节点，就把它的值按顺序加入 res。 等整棵树遍历结束后，res 里保存的就是完整的中序遍历结果。

2. inorderTraversal 函数在做什么？

public List<Integer> inorderTraversal(TreeNode root) {
    if (root != null) traversal(root);
    return res;
}

这是题目要求实现的主函数。

它的逻辑很简单：

• 如果根节点不为空，就从根节点开始递归遍历

• 最后返回结果列表

这里对空树做了一个简单判断：

if (root != null)

如果树为空，就直接返回空列表。

3. read 函数的作用是什么？

public void read(TreeNode node) {
    res.add(node.val);
}

这个函数本质上就是“访问当前节点”。

在中序遍历里，所谓“访问一个节点”，通常就是：

• 输出它的值

• 或者把它加入结果集合

你这里把这个操作单独封装成了一个 read(node) 函数，这样逻辑上也比较清楚：

• 遍历左边

• 读取当前节点

• 遍历右边

虽然这一步也完全可以直接写成：

res.add(node.val);

但单独写一个函数，也有利于让遍历结构更明显。

4. traversal 才是核心递归函数

public void traversal(TreeNode node) {
    if (node.left != null) traversal(node.left);
    read(node);
    if (node.right != null) traversal(node.right);
}

这段代码就是整道题最核心的部分。

它严格按照中序遍历的定义来写：

第一步：先遍历左子树

if (node.left != null) traversal(node.left);

第二步：访问当前节点

read(node);

第三步：遍历右子树

if (node.right != null) traversal(node.right);

这三句代码的顺序不能乱。 只要顺序一变，遍历类型就变了。

例如：

• 如果先 read(node) 再左再右，那就是前序

• 如果左、右都递归完再 read(node)，那就是后序

所以中序遍历最关键的，不是代码量，而是这三步的先后顺序。

手动模拟一遍

我们用经典例子来走一遍：

    1
     \
      2
     /
    3

调用：

inorderTraversal(root)

于是进入：

traversal(1)

处理节点 1

• 1 没有左子树，所以左边递归跳过

• 访问 1，结果列表变成：

[1]

• 然后递归遍历右子树，也就是节点 2

处理节点 2

进入：

traversal(2)

• 先遍历左子树，也就是节点 3

处理节点 3

进入：

traversal(3)

• 3 没有左子树

• 访问 3，结果列表变成：

[1,3]

• 3 也没有右子树

• 返回上一层，也就是节点 2

回到节点 2

现在左子树已经遍历完了，所以访问当前节点 2：

结果列表变成：

[1,3,2]

然后 2 没有右子树，递归结束。

最终返回结果：

[1,3,2]

这正好就是题目答案。

为什么这个方法是正确的？

因为中序遍历的定义本身就是：

左子树 -> 根节点 -> 右子树

而你的递归函数 traversal(node) 做的事情恰好就是：

1. 递归遍历左子树

2. 访问当前节点

3. 递归遍历右子树

对于任意一个节点，这个顺序都成立。 而二叉树的整棵结构就是由无数子树递归嵌套组成的，所以只要这个递归过程对每个节点都成立，最终整棵树的遍历顺序就一定正确。

因此这个方法是完全正确的。

复杂度分析

假设二叉树中一共有 n 个节点。

时间复杂度

每个节点都会被访问恰好一次，所以时间复杂度是：

O(n)

空间复杂度

递归的额外空间主要来自函数调用栈。

最坏情况下，如果树退化成链表，递归深度会达到 n，所以空间复杂度是：

O(n)

如果树比较平衡，那么递归深度大约是树高：

O(log n)

但通常最坏情况写作 O(n)。

这道题真正想考什么？

这道题表面上非常基础，但它其实在考察二叉树递归最核心的基本功。

第一，是否真正理解三种遍历顺序的区别

很多初学者会背：

• 前序：根左右

• 中序：左根右

• 后序：左右根

但真正写代码时，还是容易混。 这道题就是最直接的训练。

第二，是否理解“访问节点”和“递归左右子树”是两件事

中序遍历看起来只是三步，但这三步在逻辑上分别代表：

• 进入左子树

• 处理当前节点

• 进入右子树

把这三件事的顺序搞清楚，后面很多树题都会顺很多。

第三，是否能接受“树是一种递归结构”

很多二叉树题的递归写法其实都建立在一个共同思想上：

左子树本身就是一棵树，右子树本身也是一棵树。

所以“遍历整棵树”就可以拆成“遍历左子树 + 处理当前节点 + 遍历右子树”。

这题还有别的写法吗？

有。

除了递归写法之外，这题还有一种很经典的 迭代写法，通常会用一个栈来模拟递归过程。

迭代中序遍历的核心思路是：

• 一路向左入栈

• 弹栈访问节点

• 再转向右子树

这种写法也很重要，尤其是在面试里，很多时候会追问：

你会不会写非递归版本？

不过从理解角度来说，递归版本是最适合入门的。 因为它最能体现中序遍历本身的定义。

和前序遍历、后序遍历有什么区别？

这三种遍历的差别，核心就在于“访问根节点”的位置不同。

前序遍历

根 -> 左 -> 右

中序遍历

左 -> 根 -> 右

后序遍历

左 -> 右 -> 根

可以发现：

• 左子树和右子树始终都会递归处理

• 唯一变化的是“根节点访问的位置”

所以理解这题之后，你再去写前序、后序，其实只需要调整一行代码的位置。

总结

这道题的核心思想可以概括成一句话：

中序遍历的本质就是对每个节点都按照“左子树 -> 当前节点 -> 右子树”的顺序进行递归处理。

具体步骤就是：

1. 如果当前节点有左子树，先递归遍历左子树

2. 访问当前节点，把值加入结果列表

3. 如果当前节点有右子树，再递归遍历右子树

这样最终得到的结果，就是整棵树的中序遍历序列。

这是一道非常经典、也非常值得认真理解的二叉树基础题。 因为它会让你真正体会到：

• 树的递归到底在递归什么

• 三种深度优先遍历的区别到底是什么

• “访问节点的位置”为什么会决定遍历顺序

把这道题真正吃透之后，再去看：

• 前序遍历

• 后序遍历

• 二叉搜索树相关题目

• 树的路径类递归题

你会明显更容易抓住递归框架。

因为“二叉树的中序遍历”本身就是二叉树递归里最经典的一道入门模板题。