LeetCode 105：从前序与中序遍历序列构造二叉树（Construct Binary Tree from Preorder and Inorder Traversal）题解

Construct Binary Tree from Preorder and Inorder Traversal 是 LeetCode Hot 100 里面一道非常经典的二叉树递归题。

这道题和前面的“前序遍历”“中序遍历”“验证二叉搜索树”这些题相比，难度会明显往上走一步。因为前面更多是在“遍历”树，而这道题要求我们做的事情是：

根据遍历结果，反过来把整棵树重新构造出来。

这就意味着你不只是要会遍历顺序，还要真正理解：

前序遍历里，根节点出现在哪里
中序遍历里，左右子树是如何分开的
递归构造时，左右子树的范围怎么切

你给出的这份 Java 代码，使用的是这道题非常标准、也非常高效的一种写法：

递归 + 哈希表定位中序下标

这种写法的核心思路非常清晰：

前序遍历的第一个节点一定是当前子树的根
在中序遍历中找到这个根节点的位置
根节点左边就是左子树，右边就是右子树
再递归去构造左右子树

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

题目介绍

给定一棵二叉树的：

前序遍历结果 preorder
中序遍历结果 inorder

要求你把这棵二叉树构造出来，并返回根节点。

题目保证：

树中没有重复元素
preorder 和 inorder 一定对应同一棵合法二叉树

例如：

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

最终构造出来的二叉树是：

因为：

前序遍历是：根 -> 左 -> 右
中序遍历是：左 -> 根 -> 右

所以两种遍历结合起来，就能唯一确定整棵树。

示例

示例 1

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

输出：
[3,9,20,null,null,15,7]

对应二叉树为：

示例 2

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

输出：
[-1]

只有一个节点时，构造结果自然就是单节点树。

前序遍历和中序遍历分别告诉了我们什么？

这道题真正的关键，不是背公式，而是先搞清楚两种遍历各自提供了什么信息。

前序遍历

顺序是：

根 -> 左 -> 右

所以对于任意一棵子树来说：

前序遍历的第一个元素，一定是这棵子树的根节点。

这点非常重要，因为它直接告诉我们：

当前子树的根是谁。

中序遍历

顺序是：

左 -> 根 -> 右

所以一旦知道了根节点是谁，那么在中序遍历中：

根节点左边的部分，就是左子树
根节点右边的部分，就是右子树

这点同样非常关键，因为它告诉我们：

左右子树分别占据了哪些范围。

所以两种遍历一结合，信息就齐了：

前序负责告诉你根节点是谁
中序负责告诉你左右子树怎么切

这就是这道题能递归构造的根本原因。

核心思路

假设当前我们正在构造某一棵子树。

第一步：找根节点

前序遍历里，当前子树的第一个元素一定是根节点。

第二步：去中序遍历里定位根节点

找到根节点在中序数组中的位置后，就能知道：

左边有多少个节点属于左子树
右边有多少个节点属于右子树

第三步：递归构造左右子树

左子树对应前序中的下一段
右子树对应再往后的一段

于是整棵树就可以递归地一层层构造出来。

这正是你代码里的做法。

Java 代码

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

class Solution {
    int[] preorder;
    HashMap<Integer, Integer> dic = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;

        // 记录中序遍历中每个值对应的下标，便于 O(1) 查找
        for (int i = 0; i < inorder.length; i++) {
            dic.put(inorder[i], i);
        }

        return recur(0, 0, inorder.length - 1);
    }

    TreeNode recur(int root, int left, int right) {
        // 当前区间为空，说明子树不存在
        if (left > right) return null;

        // preorder[root] 就是当前子树的根节点
        TreeNode node = new TreeNode(preorder[root]);

        // 在中序遍历中找到根节点下标
        int i = dic.get(preorder[root]);

        // 构造左子树
        node.left = recur(root + 1, left, i - 1);

        // 构造右子树
        node.right = recur(root + i - left + 1, i + 1, right);

        return node;
    }
}

代码拆解

这段代码看上去不长，但参数设计非常巧妙。如果第一次看，最容易卡住的地方通常是：

recur(root, left, right) 这三个参数到底代表什么
为什么右子树的根下标是：

root + i - left + 1

下面一步一步来讲。

1. 为什么要用一个哈希表 `dic`？

HashMap<Integer, Integer> dic = new HashMap<>();

它的作用是：

快速找到某个节点值在中序遍历中的位置。

因为在递归过程中，我们每次都会知道当前根节点值，然后需要去中序数组里找到它，从而切分左右子树。

如果每次都在线性扫描中序数组去找这个位置，那么时间复杂度会变高。所以提前把：

值 -> 中序下标

存进哈希表，就可以做到：

O(1)

查找。

这一步是这道题高效实现的关键优化。

2. `buildTree` 函数在做什么？

public TreeNode buildTree(int[] preorder, int[] inorder) {
    this.preorder = preorder;

    for (int i = 0; i < inorder.length; i++) {
        dic.put(inorder[i], i);
    }

    return recur(0, 0, inorder.length - 1);
}

这个函数主要做了两件事：

第一件事：保存前序数组

因为后续递归中要频繁访问。

第二件事：建立中序下标映射

方便后续快速切分左右子树。

最后调用：

recur(0, 0, inorder.length - 1)

表示：

当前子树的根节点，在前序数组中的位置是 0
当前子树对应的中序范围是 [0, inorder.length - 1]

也就是说：

一开始我们要构造的就是整棵树。

3. `recur(root, left, right)` 这三个参数分别表示什么？

这是整道题最核心的地方。

TreeNode recur(int root, int left, int right)

这里的含义是：

root：当前子树根节点在 preorder 中的下标
left：当前子树在 inorder 中的左边界
right：当前子树在 inorder 中的右边界

也就是说，这个递归函数表示：

当前要构造的子树，它的根在 preorder[root]，而它在中序遍历中覆盖区间 [left, right]。

只要把这个定义想明白，后面的递归就会顺很多。

4. 为什么 `left > right` 时返回 `null`？

if (left > right) return null;

因为这表示当前子树在中序遍历中的区间已经为空了。

也就是说：

没有节点属于这棵子树
所以这棵子树不存在
应该返回空节点

这是递归的终止条件。

5. 为什么 `preorder[root]` 一定是当前子树根节点？

TreeNode node = new TreeNode(preorder[root]);

因为前序遍历的顺序就是：

根 -> 左 -> 右

所以对于任意一棵子树来说，前序遍历中它最先出现的那个元素，一定是根节点。

你这里用 root 参数直接指向这个位置，所以：

preorder[root]

就是当前子树的根值。

6. 为什么在中序遍历中找到根节点位置后，就能切左右子树？

int i = dic.get(preorder[root]);

因为中序遍历顺序是：

左 -> 根 -> 右

所以如果当前根节点在中序中的位置是 i，那么：

区间 [left, i-1] 就是左子树
区间 [i+1, right] 就是右子树

这一步就是“切树”。

它把当前大问题分成了左右两个更小的子树构造问题。

7. 为什么左子树递归写成这样？

node.left = recur(root + 1, left, i - 1);

原因很简单：

当前根节点占了 preorder[root]
在前序遍历里，根节点之后紧接着的就是左子树部分
所以左子树的根节点下标一定是：

root + 1

而左子树在中序中的范围就是：

[left, i - 1]

所以左子树递归写成：

recur(root + 1, left, i - 1)

非常自然。

8. 为什么右子树根节点下标是 `root + i - left + 1`？

这是整道题最关键、最容易卡住的地方。

node.right = recur(root + i - left + 1, i + 1, right);

我们一步一步来拆。

先想左子树有多少个节点

根节点在中序中的位置是 i，当前中序左边界是 left。

所以左子树节点数就是：

i - left

再想前序遍历的结构

当前子树的前序顺序是：

根 | 左子树 | 右子树

也就是说：

preorder[root] 是根
接下来 i - left 个位置属于左子树
再往后的那个位置，才是右子树的根

所以右子树根节点下标就是：

root + 1 + (i - left)

也就是：

root + i - left + 1

这就是这句代码的来源。

手动模拟一遍

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

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

第一步：构造整棵树

调用：

recur(0, 0, 4)

根节点是 preorder[0] = 3
在中序中找到 3 的位置是 1

所以：

左子树中序区间是 [0, 0]
右子树中序区间是 [2, 4]

第二步：构造左子树

调用：

recur(1, 0, 0)

根节点是 preorder[1] = 9
在中序中位置也是 0

所以：

左区间 [0, -1] -> 空
右区间 [1, 0] -> 空

因此节点 9 是叶子节点。

第三步：构造右子树

右子树根下标：

0 + 1 - 0 + 1 = 2

调用：

recur(2, 2, 4)

根节点是 preorder[2] = 20
在中序中位置是 3

所以：

左子树区间 [2, 2]
右子树区间 [4, 4]

第四步：继续构造节点 20 的左子树

调用：

recur(3, 2, 2)

得到节点 15。

第五步：构造节点 20 的右子树

调用：

recur(4, 4, 4)

得到节点 7。

最终整棵树就构造完成：

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

因为这两种遍历提供的信息刚好互补：

前序遍历

总能告诉我们：

当前子树的根节点是谁。

中序遍历

总能告诉我们：

左子树和右子树分别占据哪些范围。

于是每一次递归都能做两件事：

确定当前根节点
把问题拆成左右两个更小的子树构造问题

这和二叉树本身的递归结构完全一致。所以只要：

根节点选对了
左右区间切对了
递归边界处理正确

整棵树就一定能被正确构造出来。

复杂度分析

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

时间复杂度

建立哈希表需要 O(n)
每个节点都会被递归创建一次
哈希表查找根节点位置是 O(1)

所以总时间复杂度是：

O(n)

空间复杂度

主要来自：

哈希表：O(n)
递归调用栈：最坏 O(n)

所以整体空间复杂度是：

O(n)

这道题真正想考什么？

这道题表面上是在“还原二叉树”，但本质上考察的是二叉树递归构造的能力。

第一，是否真正理解前序和中序遍历的含义

如果只会背：

前序：根左右
中序：左根右

但不能把这两句话转换成“怎么切子树”，那这题就很难写出来。

第二，是否会设计递归参数

这道题的难点很大一部分不在算法本身，而在于：

递归函数到底应该传什么参数。

你这份代码里：

root
left
right

这组参数设计得非常精炼，也非常经典。

第三，是否能推清右子树根下标

这是整道题最容易卡住的公式。一旦把“左子树节点数”想清楚，这一步就不难了。

和“从中序与后序遍历序列构造二叉树”有什么关系？

这两题非常像，只是根节点出现的位置不同。

前序 + 中序

前序第一个是根
中序用来切左右

后序 + 中序

后序最后一个是根
中序同样用来切左右

所以这两题本质上属于同一类：

利用“一个遍历给根，一个遍历给左右边界”来递归构造树。

总结

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

前序遍历负责告诉我们当前子树的根节点是谁，中序遍历负责告诉我们左右子树的范围，从而可以递归地把整棵树构造出来。

具体步骤就是：

前序数组中当前子树的第一个元素就是根节点
在中序数组中找到这个根节点的位置
左边区间构成左子树，右边区间构成右子树
根据左子树节点数，推算右子树根节点在前序中的位置
递归构造左右子树

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

遍历序列不只是“输出结果”，还蕴含了树结构信息
递归构造树时，参数设计有多重要
很多树题的关键，不是代码长短，而是你是否真的理解树是如何被拆开的

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

从中序与后序遍历序列构造二叉树
序列化与反序列化二叉树
不同的二叉搜索树 II

这些树构造题时，你会明显更容易抓住套路。

因为“从前序与中序遍历序列构造二叉树”本身就是二叉树构造题里最经典的一道模板题。

LeetCode 105：从前序与中序遍历序列构造二叉树（Construct Binary Tree from Preorder and Inorder Traversal）题解

题目介绍

示例

示例 1

示例 2

前序遍历和中序遍历分别告诉了我们什么？

前序遍历

中序遍历

核心思路

第一步：找根节点

第二步：去中序遍历里定位根节点

第三步：递归构造左右子树

Java 代码

代码拆解

1. 为什么要用一个哈希表 dic？

2. buildTree 函数在做什么？

第一件事：保存前序数组

第二件事：建立中序下标映射

3. recur(root, left, right) 这三个参数分别表示什么？

4. 为什么 left > right 时返回 null？

5. 为什么 preorder[root] 一定是当前子树根节点？

6. 为什么在中序遍历中找到根节点位置后，就能切左右子树？

7. 为什么左子树递归写成这样？

8. 为什么右子树根节点下标是 root + i - left + 1？

先想左子树有多少个节点

再想前序遍历的结构

手动模拟一遍

第一步：构造整棵树

第二步：构造左子树

第三步：构造右子树

第四步：继续构造节点 20 的左子树

第五步：构造节点 20 的右子树

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

前序遍历

中序遍历

复杂度分析

时间复杂度

空间复杂度

这道题真正想考什么？

第一，是否真正理解前序和中序遍历的含义

第二，是否会设计递归参数

第三，是否能推清右子树根下标

和“从中序与后序遍历序列构造二叉树”有什么关系？

前序 + 中序

后序 + 中序

总结

发送评论 编辑评论

推荐文章

1. 为什么要用一个哈希表 `dic`？

2. `buildTree` 函数在做什么？

3. `recur(root, left, right)` 这三个参数分别表示什么？

4. 为什么 `left > right` 时返回 `null`？

5. 为什么 `preorder[root]` 一定是当前子树根节点？

8. 为什么右子树根节点下标是 `root + i - left + 1`？

发送评论编辑评论