由先序和中序序列构造二叉树：递归定位根

本文属于「408 算法拓展训练」——考纲内、真题代码题尚未考过的经典题。由遍历序列构造二叉树是「二叉树的构造」这一考点的代表题，也是理解「先序定根、中序分左右」这套还原逻辑的最佳例子。它是经典训练题，不是真题，也不押题。

题目

给定一棵二叉树的先序遍历序列和中序遍历序列（结点值互不相同），设计算法还原出这棵二叉树。例如先序序列 3 9 20 15 7、中序序列 9 3 15 20 7，还原出的树应该是：根 3，左孩子 9（叶子），右孩子 20（左孩子 15、右孩子 7）。

这道题没有「尽可能高效」的要求。按拓展训练导语的分类，它属于「直观即满分」型——遍历一遍两个序列，把树还原出来，就是这道题要求的全部。

直观解法：先序定根,中序分左右,一遍递归还原

还原的思路完全由两种遍历的定义决定：先序序列的第一个元素永远是（子）树的根；有了根，再去中序序列里找它的位置——根左边的一段是左子树的中序序列，右边的一段是右子树的中序序列。左子树有多少个结点，先序序列里紧跟根之后的那一段就是左子树的先序序列，剩下的是右子树的先序序列。递归地对左右两半重复这个过程，直到区间为空。

要让「在中序序列里找根的位置」这一步足够快，最自然的想法是提前用一个哈希表把中序序列里每个值映射到它的下标，这样定位根是 $O (1)$ ，不用每递归一层都重新扫一遍中序数组。

#include <stdlib.h>

typedef struct TreeNode {
    int data;
    struct TreeNode *left, *right;
} TreeNode;

#define MAXN 1000
int indexMap[2000];   /* 简化处理：假设结点值可直接作数组下标；实际实现常用哈希表 */

/* pre: 先序序列，pl..pr 为当前子树在先序中的区间
   in:  中序序列，il..ir 为当前子树在中序中的区间 */
TreeNode* build(int pre[], int pl, int pr, int in[], int il, int ir) {
    if (pl > pr) return NULL;                    /* 区间为空,子树不存在 */

    TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
    root->data = pre[pl];                          /* 先序首元是根 */

    int k = indexMap[pre[pl]];                     /* O(1) 定位根在中序中的下标 */
    int leftSize = k - il;                          /* 左子树的结点个数 */

    root->left  = build(pre, pl + 1, pl + leftSize, in, il, k - 1);
    root->right = build(pre, pl + leftSize + 1, pr, in, k + 1, ir);
    return root;
}

TreeNode* buildTree(int pre[], int in[], int n) {
    for (int i = 0; i < n; i++) indexMap[in[i]] = i;  /* 预处理:值->中序下标 */
    return build(pre, 0, n - 1, in, 0, n - 1);
}

拿先序 3 9 20 15 7、中序 9 3 15 20 7 走一遍：根是 3，在中序里定位到下标 1，左边 9 是左子树中序（1 个结点）、右边 15 20 7 是右子树中序（3 个结点）；先序里紧跟 3 之后的 1 个结点 9 是左子树先序，剩下 20 15 7 是右子树先序。左子树只有一个结点 9，直接是叶子；右子树递归下去，根是 20，中序里 20 左边是 15、右边是 7，还原出 20 的左孩子 15、右孩子 7。整棵树和题目给的还原结果一致。

复杂度：预处理哈希表（或题解里简化的值到下标数组）一次扫描 $O (n)$ ；递归中每个结点只做一次 $O (1)$ 的根定位和区间切分， $n$ 个结点合计 $O (n)$ ；递归栈深度等于树高，空间 $O (h)$ （不含哈希表本身的 $O (n)$ ）。

为什么它就是满分解

这道题没有「暴力 vs 最优」的分差。用总纲的「找浪费三问」审一遍，三问全部答「没有」：

有没有重复扫描？ 没有。定位根用的是提前建好的映射表，一次查表即得，不需要每递归一层都重新扫一遍中序区间。
有没有重算已知的东西？ 没有。区间的切分只用一次下标减法（leftSize = k - il）算出左子树结点数，之后先序、中序的四个子区间边界都是常数时间推出来的，没有任何值被重复计算。
有没有放着性质不用？ 没有。先序「根在最前」、中序「根分左右」这两条性质，正好被递归框架直接使用，没有额外可利用的结构被浪费。

更根本的一条：要把整棵树的结点关系还原出来，至少要把先序、中序两个长度为 $n$ 的序列都完整读一遍——这是 $O (n)$ 的下界，任何正确算法都躲不开。碰到下界，直观写法即最优。

真正的难点在下标切分

分不在优化上，在把两处下标算准：

中序里定位根：如果不用哈希表而是每次都线性扫描中序区间找根，逻辑依然正确，但会退化成「每层 $O (n)$ 、共 $n$ 层」的重复扫描，实现时要想清楚自己选的是哪种方式，复杂度分析要和代码一致。
先序区间的切分最容易算错：左子树先序区间是 [pl+1, pl+leftSize]，右子树先序区间是 [pl+leftSize+1, pr]——leftSize 算的是「中序里根左边有多少个结点」，这个数字直接决定了先序里从根之后数多少个结点是左子树。少加 1 或多加 1，切出来的区间就会整体错位，还原出结构完全不对的树，但代码不会报错，非常隐蔽。
中序区间的切分对称但独立：左子树中序区间是 [il, k-1]，右子树中序区间是 [k+1, ir]——k 本身（根的位置）既不属于左子树也不属于右子树，两处都要跳过它。

四个区间边界（pl+1、pl+leftSize、pl+leftSize+1、pr，以及 il、k-1、k+1、ir）最好在草稿纸上先画一遍再写代码，考场上手滑漏加 1 是这道题最高频的失分点。

递归定位根，看一遍

用先序 3 9 20 15 7、中序 9 3 15 20 7 演示还原过程——先在中序里定位根 3（下标 1），切出左子树中序 9 与右子树中序 15 20 7，再递归还原出完整的树：

加载可视化中...

演示为 JavaScript 版本，逻辑与上文 C 代码一一对应，用 JS 对象的哈希查找代替了 C 里简化的下标数组。

别画蛇添足

这道题结构清晰，过度设计的空间不大，但有两个常见的「想复杂了」：

真的把数组切出来传递。有的写法喜欢用 slice 之类的操作，每递归一层就真的拷贝出一段新的先序、中序子数组传给下一层——这样虽然逻辑上也对，但每层都要花时间和空间复制数组，整体退化到 $O (n^{2})$ 的时间和空间。用一对下标 (l, r) 表示区间、原数组不动，才是这道题该有的写法。
先建先序+后序再去凑中序。有先序+中序就已经能唯一确定整棵树，不需要再引入后序序列这类不存在于题目条件里的额外信息去交叉验证——多引入一种遍历序列只会让代码复杂度上升，对还原结果没有任何帮助。

下一步

看由遍历序列构造二叉树的交互演示：构造二叉树可视化
回到方法论源头：「暴力解到最优解」真题专题总纲

由先序和中序序列构造二叉树：递归定位根 ​

题目 ​

直观解法：先序定根,中序分左右,一遍递归还原 ​

为什么它就是满分解 ​

真正的难点在下标切分 ​

递归定位根，看一遍 ​

别画蛇添足 ​

下一步 ​