0094.二叉树的中序遍历

难度：🟢 简单

标签：栈、树、深度优先搜索、二叉树、递归

链接：94. 二叉树的中序遍历

题目描述

给定一个二叉树的根节点 root ，返回 中序遍历 下它的所有节点的值。

示例 1：

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

示例 2：

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

示例 3：

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

解题思路

核心思想

本题的核心是实现二叉树的 中序遍历。中序遍历的访问顺序是：左子树 -> 根节点 -> 右子树。这个顺序的特性在于，如果对一个二叉搜索树（BST）进行中序遍历，得到的节点序列将是升序排列的。

思路选择

递归法 是实现中序遍历最自然、最简洁的方式。算法的结构直接映射了中序遍历的定义，使得代码非常易于理解。

关键步骤

1. 递归的终止条件 (Base Case)：如果当前节点 root 为 null，表示到达了树的末端，没有节点可以访问，直接返回一个空数组。

2. 递归分解： a. 首先，递归地对当前节点的 左子树 进行中序遍历，获取左子树的遍历结果。 b. 然后，访问 根节点，获取其值 root.val。 c. 最后，递归地对当前节点的 右子树 进行中序遍历，获取右子树的遍历结果。

3. 结果合并：将左子树的遍历结果、根节点的值、右子树的遍历结果按顺序拼接起来，形成当前树的中序遍历序列。

代码实现

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 * this.val = (val===undefined ? 0 : val)
 * this.left = (left===undefined ? null : left)
 * this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function (root) {
    // Base Case: 节点为空，返回空数组
    if (root === null) return [];

    // 递归地组合 左 -> 根 -> 右
    return [...inorderTraversal(root.left), root.val, ...inorderTraversal(root.right)];
};

复杂度分析

• 时间复杂度：O(n) 其中 n 是树的节点总数。每个节点都会被访问一次。

• 空间复杂度：O(h) 其中 h 是树的高度。空间复杂度主要由递归调用栈的深度决定。在最坏情况下（树退化为一条链），空间复杂度为 O(n)；在最好的情况下（一个完全平衡的树），空间复杂度为 O(log n)。

相关题目

• 0144.二叉树的前序遍历

• 0145.二叉树的后序遍历

• 0102.二叉树的层序遍历

• 0098.验证二叉搜索树

总结

中序遍历是三种深度优先遍历（前序、中序、后序）中最常用的一种，是理解树结构和递归思想的基石。其递归解法简洁明了，完美地体现了分治策略。除了递归，中序遍历也可以通过迭代（使用栈）的方式实现，这同样是面试中常见的要求。