106. 从中序与后序遍历序列构造二叉树

题目描述

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

inorder 是二叉树的中序遍历
postorder 是同一棵树的后序遍历

请你构造并返回这棵二叉树。

示例 1

text

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

示例 2

text

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

约束

1 <= inorder.length <= 3000
postorder.length == inorder.length
-3000 <= inorder[i], postorder[i] <= 3000
inorder 和 postorder 都由互不相同的值组成
postorder 中每一个值都在 inorder 中
inorder 保证是树的中序遍历
postorder 保证是树的后序遍历

核心思路

这题和 105 很像，只是换了一种遍历组合：

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

所以这题最关键的观察是：

后序数组当前这一段的最后一个元素，一定是这棵子树的根
在中序数组中找到这个根的位置
根左边是左子树，根右边是右子树
根据左子树大小和右子树大小，切分后序数组

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

解法一：递归 + 区间下标（推荐）
解法二：递归 + 后序指针倒着推进

解法一：递归 + 区间下标

这是最标准、最推荐记住的写法。

思路拆解

假设：

text

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

后序最后一个元素 3 一定是整棵树的根。

在中序里找到 3：

text

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

那么：

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

左子树大小是 1，右子树大小是 3。

于是后序数组也能切开：

左子树后序：[9]
右子树后序：[15, 7, 20]
最后一个 3 是根

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

一步一步写出算法

第一步：先建立中序下标表

我们需要频繁在中序数组中查找根节点位置，所以先建一个 Map。

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

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

我们定义：

build(inLeft, inRight, postLeft, postRight)

表示：

用 inorder[inLeft...inRight]
和 postorder[postLeft...postRight]
构造当前子树并返回根节点

第三步：写递归终止条件

如果区间为空，说明没有子树。

if (inLeft > inRight) {
    return null
}

第四步：确定根节点

后序区间最后一个元素就是根。

const rootValue = postorder[postRight]
const root = new TreeNode(rootValue)

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

const inorderRootIndex = indexMap.get(rootValue)!

于是：

const leftSize = inorderRootIndex - inLeft
const rightSize = inRight - inorderRootIndex

第六步：递归构造左子树

中序左子树范围：

text

inLeft ~ inorderRootIndex - 1

后序左子树范围：

text

postLeft ~ postLeft + leftSize - 1

代码：

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

第七步：递归构造右子树

中序右子树范围：

text

inorderRootIndex + 1 ~ inRight

后序右子树范围：

text

postLeft + leftSize ~ postRight - 1

代码：

root.right = build(
    inorderRootIndex + 1,
    inRight,
    postLeft + leftSize,
    postRight - 1,
)

第八步：返回根节点

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(inorder: number[], postorder: number[]): TreeNode | null {
    const indexMap = new Map<number, number>()
    for (let i = 0; i < inorder.length; i++) {
        indexMap.set(inorder[i], i)
    }

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

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

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

        root.right = build(
            inorderRootIndex + 1,
            inRight,
            postLeft + leftSize,
            postRight - 1,
        )

        return root
    }

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

复杂度分析

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

其中：

哈希表是 O(n)
递归栈最坏可能到 O(n)

这一解法的优缺点

优点：

边界最清晰
和 105 的写法非常对应
面试里最好讲清楚

缺点：

区间边界稍多
后序右子树和左子树范围容易写错

解法二：递归 + 后序指针倒着推进

这个做法和 105 的“前序指针推进”是对称的。

思路拆解

后序遍历顺序是：

text

左 -> 右 -> 根

如果我们从后往前看，就变成：

text

根 -> 右 -> 左

这意味着：

用一个 postIndex 指向后序数组末尾
每次先取 postorder[postIndex] 作为当前根
postIndex--
然后要 先构造右子树，再构造左子树

这是这题最关键的地方。

为什么先右后左？

因为后序倒着读的顺序是：

text

根 -> 右 -> 左

如果你先递归左子树，顺序就乱了。

一步一步写出算法

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

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

第二步：定义后序指针

let postIndex = postorder.length - 1

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

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

build(inLeft, inRight)

表示：

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

第四步：写递归终止条件

if (inLeft > inRight) {
    return null
}

第五步：读取当前根节点

const rootValue = postorder[postIndex]
postIndex--
const root = new TreeNode(rootValue)

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

const inorderRootIndex = indexMap.get(rootValue)!

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

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

顺序一定不能反。

代码实现（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(inorder: number[], postorder: number[]): TreeNode | null {
    const indexMap = new Map<number, number>()
    for (let i = 0; i < inorder.length; i++) {
        indexMap.set(inorder[i], i)
    }

    let postIndex = postorder.length - 1

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

        const rootValue = postorder[postIndex]
        postIndex--

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

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

        return root
    }

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

复杂度分析

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

和第一种做法本质一致，只是参数设计不同。

这一解法的优缺点

优点：

参数更少
很适合和 105 放在一起对照理解
能更深地理解“遍历顺序决定递归顺序”

缺点：

postIndex 是隐式状态
很容易忘记必须先构造右子树

两种解法对比

解法	时间复杂度	空间复杂度	特点
递归 + 区间下标	`O(n)`	`O(n)`	最标准，边界更清楚
递归 + 后序指针	`O(n)`	`O(n)`	参数更少，但递归顺序更关键

如果你刚做完 105，建议把这题和 105 对照着记。

105：前序第一个是根，所以递归时 先左后右
106：后序最后一个是根，倒着读是“根右左”，所以递归时 先右后左

手动模拟一遍

以：

text

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

为例。

第一步：确定根节点

后序最后一个元素是：

text

所以整棵树的根是 3。

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

中序里 3 的位置：

text

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

所以：

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

第三步：看右子树

去掉根以后，后序右侧那一段是：

text

[15, 7, 20]

它的最后一个元素 20 是右子树根。

在中序右半部分 [15,20,7] 中：

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

所以：

20.left = 15
20.right = 7

第四步：左子树

左子树就是：

text

[9]

所以 3.left = 9。

最终构造出的树是：

text

面试时最容易错的点

1. 后序遍历里“根在最后”

这题和 105 最大的区别就在这里。

105：前序第一个是根
106：后序最后一个是根

2. 指针法里一定要先右后左

这是最容易错的点。

因为后序倒着看是：

text

根 -> 右 -> 左

所以代码必须写成：

root.right = build(...)
root.left = build(...)

不能反。

3. 左右子树区间别切错

尤其是区间写法里：

左子树后序长度是 leftSize
右子树后序紧挨着根的前面

这部分建议你自己手动画一下下标，会更稳。

4. 没有哈希表会退化

如果每次都在中序里找根位置，可能退化成 O(n^2)。

所以最好先建 Map。

一句话总结

这题的本质是：

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

想写得最稳：用 递归 + 区间下标
想和 105 对照理解：用 递归 + 后序指针倒推

106. 从中序与后序遍历序列构造二叉树

题目描述

示例 1

示例 2

约束

核心思路

解法一：递归 + 区间下标

思路拆解

一步一步写出算法

第一步：先建立中序下标表

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

第三步：写递归终止条件

第四步：确定根节点

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

第六步：递归构造左子树

第七步：递归构造右子树

第八步：返回根节点

代码实现（TypeScript）

复杂度分析

这一解法的优缺点

解法二：递归 + 后序指针倒着推进

思路拆解

一步一步写出算法

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

第二步：定义后序指针

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

第四步：写递归终止条件

第五步：读取当前根节点

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

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

代码实现（TypeScript）

复杂度分析

这一解法的优缺点

两种解法对比

手动模拟一遍

第一步：确定根节点

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

第三步：看右子树

第四步：左子树

面试时最容易错的点

1. 后序遍历里“根在最后”

2. 指针法里一定要先右后左

3. 左右子树区间别切错

4. 没有哈希表会退化

一句话总结

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