94. 二叉树的中序遍历

Origin: LeetCode 94

题目描述

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

示例

Input: root = [1, null, 2, 3] Output: [1, 3, 2]

    1
     \
      2
     /
    3

Input: root = [] Output: []

Input: root = [1] Output: [1]

约束

• 树中节点数目范围是 [0, 100]
• -100 <= Node.val <= 100

关键信息

• 中序遍历：左 → 根 → 右
• 递归最简单，迭代用栈
• 二叉树节点结构：val + left + right

Resolution

我的解法

function inorderTraversal(root: TreeNode | null): number[] {
    if (!root) return []
    const result: number[] = []
    const recursion = (node: TreeNode | null) => {
        if (!node) return
        if (node.left) {
            recursion(node.left)
        }
        result.push(node.val)
        if (node.right) {
            recursion(node.right)
        }
    }
    recursion(root)
    return result
}

解题思路

中序遍历：左 → 根 → 右。递归最直观：

1. 递归左子树
2. 读当前节点值
3. 递归右子树

result 数组在外部定义，递归函数往里 push，避免递归返回值合并。

调整 push 的位置即可实现三种遍历：

• 前序（根左右）：先 push，再递归左，再递归右
• 中序（左根右）：先递归左，再 push，再递归右
• 后序（左右根）：先递归左，再递归右，再 push

复杂度

• 时间：O(n)，每个节点访问一次
• 空间：O(h)，h 是树高，递归栈深度