算法

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

loser

30 Aug 2026 • 9 min read

给定两个整数数组 preorder 和 inorder，其中 preorder 是二叉树的先序遍历，inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

先序遍历顺序是：

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

中序遍历顺序是：

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

示例 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]

提示：

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 均无重复元素
inorder 中的每个元素都出现在 preorder 中
preorder 保证为某棵二叉树的先序遍历序列
inorder 保证为同一棵二叉树的中序遍历序列

解法（递归 + 哈希表）：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    unordered_map<int, int> inorderIndex;
    int preorderIndex = 0;

public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        inorderIndex.clear();
        preorderIndex = 0;

        int n = inorder.size();
        for (int i = 0; i < n; ++i)
        {
            inorderIndex[inorder[i]] = i;
        }

        return build(preorder, 0, n - 1);
    }

private:
    TreeNode* build(vector<int>& preorder, int inLeft, int inRight) {
        if (inLeft > inRight)
        {
            return nullptr;
        }

        int rootValue = preorder[preorderIndex++];
        int rootIndex = inorderIndex[rootValue];

        TreeNode* root = new TreeNode(rootValue);
        root->left = build(preorder, inLeft, rootIndex - 1);
        root->right = build(preorder, rootIndex + 1, inRight);

        return root;
    }
};

核心思想

先序遍历的第一个节点一定是当前子树的根节点。

拿到根节点后，再去中序遍历中找到它的位置。

中序遍历中，根节点左侧的部分就是左子树，根节点右侧的部分就是右子树。

这题最关键的观察是：

先序遍历负责确定“当前子树的根是谁”，中序遍历负责确定“左子树和右子树的范围”。

例如：

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

先序遍历第一个元素 3 是根节点。

在中序数组中，3 的位置是 1：

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

接下来，先序遍历中紧跟在 3 后面的元素 9 就是左子树的根节点，之后的 20 就是右子树的根节点。

递归执行同样的过程，就能构造整棵树。

哈希表存什么

如果每次都在 inorder 中顺序查找根节点位置，最坏时间复杂度会达到 O(n^2)。

因此先用哈希表保存每个节点值在中序数组中的下标：

unordered_map<int, int> inorderIndex;

其中：

键：节点值
值：节点值在 inorder 中的下标

例如：

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

哈希表中保存：

9  -> 0
3  -> 1
15 -> 2
20 -> 3
7  -> 4

因为题目保证节点值互不相同，所以每个节点值对应唯一的中序位置。

查询 inorderIndex[rootValue] 的平均时间复杂度是 O(1)。

递归区间含义

递归函数：

build(preorder, inLeft, inRight)

表示：

使用 preorder 中尚未处理的节点，构造 inorder 下标范围 [inLeft, inRight] 对应的子树

这里用中序数组区间表示当前子树包含哪些节点。

如果：

inLeft > inRight

说明当前区间为空，没有节点可以构造，返回 nullptr。

如果区间不为空：

从 preorder 中取出下一个节点作为根节点。
在哈希表中找到根节点在 inorder 中的位置 rootIndex。
递归构造中序区间 [inLeft, rootIndex - 1]，作为左子树。
递归构造中序区间 [rootIndex + 1, inRight]，作为右子树。

为什么先构造左子树再构造右子树

先序遍历顺序是：

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

所以当前根节点确定后，preorderIndex 指向的下一个节点一定是当前根节点左子树的根节点，前提是左子树不为空。

因此必须先递归构造左子树。

左子树构造完成后，preorderIndex 才会移动到右子树的根节点。

如果先构造右子树，就会错误地把先序遍历中属于左子树的节点当成右子树根节点。

中序区间则负责判断左子树是否为空：

如果 rootIndex > inLeft，左区间非空，存在左子树。
如果 rootIndex == inLeft，左区间为空，没有左子树。

为什么只需要一个先序指针

在每次递归中，当前子树的根节点总是先序遍历中尚未使用的第一个节点。

因此不需要为每个递归区间单独传递先序左右边界。

只要使用一个全局的 preorderIndex，每次创建根节点时向后移动一次即可：

int rootValue = preorder[preorderIndex++];

由于递归严格按照“根、左、右”的顺序执行，先序数组中的节点会被依次分配给正确的子树。

为什么不需要修改两个数组

算法只读取 preorder 和 inorder 的内容：

preorder 用来按顺序取根节点
inorder 用来确定左右子树范围

节点本身通过 new TreeNode 创建，左右子树通过指针连接。

所以不需要删除、移动或修改输入数组中的元素。

边界情况

如果树只有一个节点：

preorder = [-1]
inorder = [-1]

先序指针取出 -1，中序区间左右边界都为 0，左右子树区间都为空，最终返回只有根节点的树。

如果当前根节点在中序数组的最左侧，说明当前子树没有左子树，只递归构造右子树。

如果当前根节点在中序数组的最右侧，说明当前子树没有右子树，只递归构造左子树。

如果整棵树退化成一条左链或右链，递归区间会逐步缩小到单个元素，仍然可以正确构造。

题目保证两个遍历序列来自同一棵树，且节点值没有重复，所以不需要处理无法构造或定位不唯一的情况。

正确性证明

我们证明：算法能够根据 preorder 和 inorder 正确构造原二叉树。

结论 1：每次递归选择的节点都是当前子树的根节点

先序遍历的定义是先访问根节点，再访问左子树和右子树。

因此，对于当前尚未构造的子树，preorderIndex 指向的第一个未使用元素一定是该子树的根节点。

算法每次执行：

int rootValue = preorder[preorderIndex++];

把这个元素创建为当前子树的根节点。

递归构造左子树和右子树时，左子树先被处理，正好符合先序遍历中根、左、右的顺序。

所以每次递归选择的根节点都是正确的。

结论 2：中序位置能正确划分左右子树

设当前根节点值为 rootValue，它在中序数组中的位置为 rootIndex。

中序遍历顺序是：

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

因此：

[inLeft, rootIndex - 1] 中的所有节点属于左子树
rootIndex 位置是当前根节点
[rootIndex + 1, inRight] 中的所有节点属于右子树

算法正是按照这三个范围递归连接节点。

所以左右子树划分正确。

结论 3：递归不会漏掉或重复使用节点

每创建一个节点，preorderIndex 恰好增加 1，所以每个先序元素最多被使用一次。

对于当前中序区间，根节点位置会把区间分成两个互不重叠的区间：

[inLeft, rootIndex - 1]
[rootIndex + 1, inRight]

两个子区间不包含当前根节点，也不会互相重叠。

递归继续处理这两个区间，直到区间为空。

因此每个节点都会被构造一次，且不会重复构造或遗漏。

结论 4：构造出的树满足给定的两种遍历顺序

算法先将当前节点作为根节点，再递归构造左子树，最后递归构造右子树。

所以构造出的树的先序遍历顺序与 preorder 一致。

同时，左子树由根节点在中序数组左侧的元素构造，当前根节点位于中间，右子树由右侧元素构造。

所以构造出的树的中序遍历顺序与 inorder 一致。

得出结论

由结论 1 可知，每个递归步骤都选择了正确的根节点。

由结论 2 可知，每个根节点都正确划分了左右子树。

由结论 3 可知，所有节点都会被恰好构造一次。

由结论 4 可知，构造出的树同时满足给定的先序和中序遍历顺序。

因此算法能够正确构造并返回原二叉树。

举例理解

以：

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

为例。

第一步：构造根节点 `3`

先序第一个元素是 3，所以根节点是 3。

3 在中序数组中的下标是 1：

左区间：[9]
根节点：3
右区间：[15,20,7]

因此左子树范围是 [0,0]，右子树范围是 [2,4]。

第二步：构造左子树

先序指针移动到 9。

当前左区间只有 [9]，所以 9 是节点 3 的左孩子。

它在中序中的左右区间都为空，左子树构造完成。

第三步：构造右子树

先序指针继续移动到 20。

在当前右区间 [15,20,7] 中，20 是根节点。

它在中序中的位置把区间分成：

左区间：[15]
根节点：20
右区间：[7]

所以 15 是 20 的左孩子，7 是 20 的右孩子。

最终构造出的树是：

它的先序遍历是：

[3,9,20,15,7]

中序遍历是：

[9,3,15,20,7]

与输入完全一致。

复杂度分析

设二叉树节点数为 n。

构建哈希表需要遍历一次 inorder，时间复杂度为 O(n)。

递归过程中每个节点只会创建和处理一次，时间复杂度为 O(n)。

所以总时间复杂度是：

O(n)

哈希表需要保存 n 个节点值与中序下标的映射。

递归调用栈的深度为树高 h，空间复杂度为 O(h)。

因此总空间复杂度是：

O(n + h)

由于 h <= n，通常写作：