105. 从前序与中序遍历序列构造二叉树

题目描述

给定两个整数数组 preorder 和 inorder，其中：

preorder 是二叉树的前序遍历
inorder 是同一棵树的中序遍历

请构造二叉树并返回其根节点。

示例 1

text

输入：preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出：[3,9,20,null,null,15,7]

示例 2

text

输入：preorder = [-1], inorder = [-1]
输出：[-1]

约束

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 均无重复元素
inorder 均出现在 preorder
preorder 保证为二叉树的前序遍历序列
inorder 保证为二叉树的中序遍历序列

什么是前序遍历和中序遍历

在二叉树里，所谓“遍历”，就是按照某种固定顺序把所有节点访问一遍。

前序遍历

前序遍历的顺序是：

text

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

也就是说，每到一棵树时，第一件事先看根，再看左边，最后看右边。

比如这棵树：

text

它的前序遍历结果是：

text

[3, 9, 20, 15, 7]

因为访问顺序是：

text

3 -> 9 -> 20 -> 15 -> 7

中序遍历

中序遍历的顺序是：

text

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

也就是说，每到一棵树时，要先把左边看完，再看根，最后看右边。

还是上面这棵树：

text

它的中序遍历结果是：

text

[9, 3, 15, 20, 7]

因为访问顺序是：

text

9 -> 3 -> 15 -> 20 -> 7

后序遍历

后序遍历的顺序是：

text

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

也就是说，每到一棵树时，要先把左右子树都处理完，最后再访问根节点。

还是上面这棵树：

text

它的后序遍历结果是：

text

[9, 15, 7, 20, 3]

因为访问顺序是：

text

9 -> 15 -> 7 -> 20 -> 3

为什么这题要同时给前序和中序？

因为它们分别提供了两种不同的信息：

前序遍历告诉我们：当前子树的根是谁
中序遍历告诉我们：根节点左边是左子树，右边是右子树

所以两者结合起来，就能把整棵树唯一确定出来。

顺便也可以对比记忆三种常见遍历：

前序：根 -> 左 -> 右
中序：左 -> 根 -> 右
后序：左 -> 右 -> 根

核心思路

这题的关键是把两种遍历序列的特点用起来：

前序遍历：根 -> 左子树 -> 右子树
中序遍历：左子树 -> 根 -> 右子树

所以每次构造子树时：

前序数组当前这一段的第一个元素，一定是这棵子树的根
在中序数组里找到这个根的位置
根左边就是左子树，根右边就是右子树
根据左子树节点数，可以切分出前序数组中左子树和右子树的范围

这题至少有两种常见做法：

解法一：递归 + 数组区间下标（推荐）
解法二：递归 + 前序指针推进

解法一：递归 + 数组区间下标

这是最经典、最推荐掌握的写法。

思路拆解

假设：

text

preorder = [3, 9, 20, 15, 7]
inorder  = [9, 3, 15, 20, 7]

前序第一个元素 3 一定是整棵树的根。

然后去中序里找 3：

text

[9, 3, 15, 20, 7]
    ^

那么：

左边 [9] 是左子树
右边 [15, 20, 7] 是右子树

左子树节点数是 1，所以前序里：

根后面的 1 个元素属于左子树，也就是 [9]
剩下的是右子树，也就是 [20, 15, 7]

然后继续递归构造左右子树即可。

为什么一定能这样分？

因为题目说了：

所有值都 不重复

这意味着：

根节点值在中序数组中的位置是唯一的
左右子树的边界也就唯一确定了

所以我们只要不断递归切分区间，就能唯一构造出整棵树。

一步一步写出算法

第一步：先建一个哈希表

因为每次都要在中序数组里找根节点的位置。

如果每次都线性查找，会比较慢。

所以先用 Map 记录：

const indexMap = new Map<number, number>()
for (let i = 0; i < inorder.length; i++) {
    indexMap.set(inorder[i], i)
}

这样后面查一个值在中序里的下标就是 O(1)。

第二步：定义递归函数含义

我们定义：

build(preLeft, preRight, inLeft, inRight)

表示：

用 preorder[preLeft...preRight]
和 inorder[inLeft...inRight]
构造当前子树，并返回根节点

第三步：写递归终止条件

如果区间为空，就说明这棵子树不存在。

if (preLeft > preRight) {
    return null
}

第四步：先确定根节点

前序区间的第一个元素就是根。

const rootValue = preorder[preLeft]
const root = new TreeNode(rootValue)

第五步：在中序里找到根的位置

const inorderRootIndex = indexMap.get(rootValue)!

那么左子树大小就是：

const leftSize = inorderRootIndex - inLeft

第六步：递归构造左子树

前序里左子树范围是：

text

preLeft + 1 ~ preLeft + leftSize

中序里左子树范围是：

text

inLeft ~ inorderRootIndex - 1

代码：

root.left = build(
    preLeft + 1,
    preLeft + leftSize,
    inLeft,
    inorderRootIndex - 1,
)

第七步：递归构造右子树

前序里右子树范围是：

text

preLeft + leftSize + 1 ~ preRight

中序里右子树范围是：

text

inorderRootIndex + 1 ~ inRight

代码：

root.right = build(
    preLeft + leftSize + 1,
    preRight,
    inorderRootIndex + 1,
    inRight,
)

第八步：返回根节点

return root

代码实现（TypeScript）

class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = val ?? 0
        this.left = left ?? null
        this.right = right ?? null
    }
}

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
    const indexMap = new Map<number, number>()
    for (let i = 0; i < inorder.length; i++) {
        indexMap.set(inorder[i], i)
    }

    const build = (
        preLeft: number,
        preRight: number,
        inLeft: number,
        inRight: number,
    ): TreeNode | null => {
        if (preLeft > preRight) {
            return null
        }

        const rootValue = preorder[preLeft]
        const root = new TreeNode(rootValue)
        const inorderRootIndex = indexMap.get(rootValue)!
        const leftSize = inorderRootIndex - inLeft

        root.left = build(
            preLeft + 1,
            preLeft + leftSize,
            inLeft,
            inorderRootIndex - 1,
        )

        root.right = build(
            preLeft + leftSize + 1,
            preRight,
            inorderRootIndex + 1,
            inRight,
        )

        return root
    }

    return build(0, preorder.length - 1, 0, inorder.length - 1)
}

复杂度分析

时间复杂度：O(n)
空间复杂度：O(n)

其中：

哈希表需要 O(n)
递归调用栈最坏也可能到 O(n)

这一解法的优缺点

优点：

逻辑清晰
是最标准的模板写法
面试里最好讲清楚

缺点：

需要认真想清楚区间边界
左右子树范围很容易写错一个 +1 或 -1

解法二：递归 + 前序指针推进

这个做法的特点是：

不用显式切前序区间，而是用一个全局指针不断读取前序数组。

思路拆解

前序遍历顺序是：

text

根 -> 左 -> 右

所以我们可以维护一个 preIndex，表示“当前要处理的根节点是谁”。

每次递归时：

用 preorder[preIndex] 创建当前根节点
preIndex++
根据这个根节点在中序中的位置，把当前中序区间切成左右两部分
先递归构造左子树
再递归构造右子树

这样也能把树构建出来。

一步一步写出算法

第一步：仍然先建中序下标表

const indexMap = new Map<number, number>()
for (let i = 0; i < inorder.length; i++) {
    indexMap.set(inorder[i], i)
}

第二步：定义前序指针

let preIndex = 0

它表示：当前该从前序数组哪个位置取根节点。

第三步：递归函数只维护中序范围

因为前序范围不再显式传递，所以递归函数只需要知道：

build(inLeft, inRight)

表示用中序区间 [inLeft, inRight] 构造一棵子树。

第四步：递归终止条件

if (inLeft > inRight) {
    return null
}

第五步：读取当前根节点

const rootValue = preorder[preIndex]
preIndex++
const root = new TreeNode(rootValue)

第六步：在中序中找到根的位置

const inorderRootIndex = indexMap.get(rootValue)!

第七步：先构造左子树，再构造右子树

root.left = build(inLeft, inorderRootIndex - 1)
root.right = build(inorderRootIndex + 1, inRight)

为什么必须先左后右？

因为前序遍历本来就是：

text

根 -> 左 -> 右

如果你先递归右子树，preIndex 推进顺序就乱了。

代码实现（TypeScript）

class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = val ?? 0
        this.left = left ?? null
        this.right = right ?? null
    }
}

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
    const indexMap = new Map<number, number>()
    for (let i = 0; i < inorder.length; i++) {
        indexMap.set(inorder[i], i)
    }

    let preIndex = 0

    const build = (inLeft: number, inRight: number): TreeNode | null => {
        if (inLeft > inRight) {
            return null
        }

        const rootValue = preorder[preIndex]
        preIndex++

        const root = new TreeNode(rootValue)
        const inorderRootIndex = indexMap.get(rootValue)!

        root.left = build(inLeft, inorderRootIndex - 1)
        root.right = build(inorderRootIndex + 1, inRight)

        return root
    }

    return build(0, inorder.length - 1)
}

复杂度分析

时间复杂度：O(n)
空间复杂度：O(n)

和第一种做法本质上一样，只是递归参数设计不同。

这一解法的优缺点

优点：

参数更少
代码更紧凑
更贴近“前序不断取根”的本质

缺点：

preIndex 是隐式状态
第一次写时更容易对递归过程失去掌控感

两种解法对比

解法	时间复杂度	空间复杂度	特点
递归 + 区间下标	`O(n)`	`O(n)`	最标准，边界更明确
递归 + 前序指针	`O(n)`	`O(n)`	参数更少，写法更紧凑

如果你是第一次做这题，建议优先把第一种写法彻底搞懂。

手动模拟一遍

以：

text

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

为例。

第一步：确定根节点

前序第一个元素是：

text

所以整棵树根节点是 3。

第二步：在中序中切分左右子树

中序里 3 的位置：

text

[9, 3, 15, 20, 7]
    ^

所以：

左子树中序：[9]
右子树中序：[15,20,7]

第三步：确定左子树

左子树大小为 1，所以前序里根后面一个元素：

text

[9]

就是左子树。

于是左孩子是 9。

第四步：确定右子树

剩下前序：

text

[20,15,7]

右子树根是 20。

在中序右半部分：

text

[15,20,7]

中，20 左边 [15] 是左子树，右边 [7] 是右子树。

所以：

20.left = 15
20.right = 7

最终构造出的树就是：

text

面试时最容易错的点

1. 一定要先理解“谁决定根节点”

前序第一个元素，一定是当前子树根节点
中序用来切分左右子树

这两个角色不要搞反。

2. 左子树节点数量一定要算对

const leftSize = inorderRootIndex - inLeft

这个值非常关键，因为它决定了前序数组左右子树的边界。

3. 没有哈希表会退化

如果你每次都在中序数组里线性找根节点位置：

每层递归都可能 O(n) 查找
总复杂度可能退化到 O(n^2)

所以建议先建 Map。

4. 题目能唯一构造的前提是“没有重复值”

如果有重复值，那么根节点在中序中的位置就不唯一，树结构也就不唯一。

一句话总结

这题的本质是：

前序负责告诉你“根是谁”，中序负责告诉你“左右子树怎么切”。

想写得最稳：用 递归 + 区间下标
想写得更紧凑：用 递归 + 前序指针

105. 从前序与中序遍历序列构造二叉树

题目描述

示例 1

示例 2

约束

什么是前序遍历和中序遍历

前序遍历

中序遍历

后序遍历

为什么这题要同时给前序和中序？

核心思路

解法一：递归 + 数组区间下标

思路拆解

为什么一定能这样分？

一步一步写出算法

第一步：先建一个哈希表

第二步：定义递归函数含义

第三步：写递归终止条件

第四步：先确定根节点

第五步：在中序里找到根的位置

第六步：递归构造左子树

第七步：递归构造右子树

第八步：返回根节点

代码实现（TypeScript）

复杂度分析

这一解法的优缺点

解法二：递归 + 前序指针推进

思路拆解

一步一步写出算法

第一步：仍然先建中序下标表

第二步：定义前序指针

第三步：递归函数只维护中序范围

第四步：递归终止条件

第五步：读取当前根节点

第六步：在中序中找到根的位置

第七步：先构造左子树，再构造右子树

代码实现（TypeScript）

复杂度分析

这一解法的优缺点

两种解法对比

手动模拟一遍

第一步：确定根节点

第二步：在中序中切分左右子树

第三步：确定左子树

第四步：确定右子树

面试时最容易错的点

1. 一定要先理解“谁决定根节点”

2. 左子树节点数量一定要算对

3. 没有哈希表会退化

4. 题目能唯一构造的前提是“没有重复值”

一句话总结

推荐你最后记住的标准写法