由遍历序列构造二叉树

2026 大纲 四（二）3 二叉树的遍历 · "反问题"部分：已知遍历序列还原二叉树（三种遍历本身见《前序遍历》《中序遍历》《后序遍历》《层序遍历》）。

反问题：还原一棵树要两件信息

遍历是"给树，求序列"；这一篇是反过来——给序列，求树。

还原一棵二叉树，需要回答两个问题：谁是根，以及左右子树各占哪些结点。四种遍历序列各自只回答其中一个：

序列	能提供	不能提供
前序（NLR）	首元素是根；每棵子树占一段连续区间，且区间首元素是该子树的根	左右子树的分界位置
后序（LRN）	末元素是根；每棵子树占一段连续区间，区间末元素是该子树的根	左右子树的分界位置
层序	首元素是根；每棵子树的元素保持相对次序（但不连续）	左右子树的分界
中序（LNR）	根把序列一分为二：根左边全在左子树、右边全在右子树	谁是根（要靠别的序列告诉）

前序、后序、层序都只解决"谁是根"，中序只解决"左右怎么分"。 两个问题都要解决，所以能唯一确定的组合必然是"一个定根的 + 中序"：

$$\text{前序}+\text{中序}✓\text{后序}+\text{中序}✓\text{层序}+\text{中序}✓$$$$\text{前序}+\text{后序}\times \text{前序}+\text{层序}\times \text{后序}+\text{层序}\times$$

前序 + 后序是两把同样的钥匙配同一把锁，另一把锁没人开。

中序这份"划分能力"的根源是二叉树严格区分左右——正因为左子树的结点必须全部排在根之前、右子树全部排在根之后，一个根才能把序列切干净。其他次序都做不到。

全篇有一个前提：各结点的值互不相同。 有重复值时，"在中序里定位根"就会出现歧义，下面所有唯一性的讨论都失效。

先看一眼

加载可视化中...

前序 + 中序：三步法

定根 → 在中序中定位根、左右一分为二 → 按左子树结点数切另一条序列，递归。 子序列为空就返回 NULL。

以前序 ABDECFG、中序 DBEAFCG 为例：

步骤	操作	前序序列	中序序列	确定的根
1	取前序首元素 A 为根；中序中 A 左侧 DBE（3 个）为左子树、FCG 为右子树	A BDECFG	DBE A FCG	A
2	左子树：前序取 A 之后的 3 个 = BDE，中序 DBE → 根为 B，左 D、右 E	B DE	D B E	B
3	右子树：前序剩下 CFG，中序 FCG → 根为 C，左 F、右 G	C FG	F C G	C
4	D、E、F、G 的子序列均为空，递归结束	—	—	D E F G

        A
       / \
      B   C
     / \ / \
    D  E F  G

整个过程的关键量是左子树结点数 $L$，而它只能从中序里数（根左边有几个元素）——不能从前序里"看着像"来估。切错 $L$ 是这类题最主要的失分方式。

typedef struct TreeNode {
    char val;
    struct TreeNode *left, *right;
} TreeNode;

// pre: 前序序列, in: 中序序列
// pl,pr: 前序子序列范围; il,ir: 中序子序列范围
TreeNode* buildFromPreIn(char pre[], int pl, int pr,
                         char in[],  int il, int ir) {
    if (pl > pr) return NULL;                       // 子序列为空：空子树
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = pre[pl];                            // 前序首元素是根
    int k;
    for (k = il; k <= ir; k++)                      // 在中序中定位根
        if (in[k] == pre[pl]) break;
    int leftLen = k - il;                           // 左子树结点数，只能从中序里数
    // 前序中：根之后的 leftLen 个是左子树，再往后是右子树
    root->left  = buildFromPreIn(pre, pl + 1,           pl + leftLen, in, il,    k - 1);
    root->right = buildFromPreIn(pre, pl + leftLen + 1, pr,           in, k + 1, ir);
    return root;
}

四个下标是最容易写错的地方，核对一遍：左子树的前序范围 $[pl+1,pl+L]$ 与中序范围 $[il,k-1]$ 长度都是 $L$；右子树的前序范围 $[pl+L+1,pr]$ 与中序范围 $[k+1,ir]$ 长度都是 $ir-k$。$L=0$ 时左子树的前序范围是 $[pl+1,pl]$，满足 pl > pr 直接返回 NULL。

还原完一定要回代验证：对结果重做一次前序与中序遍历，与题目给的两条序列逐字对上。这一步能挡住绝大多数切分错误。上例回代得 ABDECFG 与 DBEAFCG，一致 ✓

后序 + 中序：完全对称

后序末元素是根，其余逻辑与前序 + 中序一模一样。以后序 DEBFGCA、中序 DBEAFCG 为例：取后序末元素 A 为根，中序划分为左 DBE、右 FCG；左子树取后序的前 3 个 DEB → 根为 B；右子树取剩下的 FGC → 根为 C。构造结果与上一节相同。

TreeNode* buildFromPostIn(char post[], int pl, int pr,
                          char in[],   int il, int ir) {
    if (pl > pr) return NULL;
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = post[pr];                     // 后序最后一个元素是根
    int k;
    for (k = il; k <= ir; k++)
        if (in[k] == post[pr]) break;
    int leftLen = k - il;
    // 后序中：前 leftLen 个是左子树，接着是右子树，最后一个才是根
    root->left  = buildFromPostIn(post, pl,           pl + leftLen - 1, in, il,    k - 1);
    root->right = buildFromPostIn(post, pl + leftLen, pr - 1,           in, k + 1, ir);
    return root;
}

层序 + 中序：不能按位置切，要按归属筛

层序首元素是根，这一步和前序一样。但接下来不能照抄——前序、后序里子树的元素是连续的一段，可以按 $L$ 直接切；层序里左右子树的元素是交替出现的（同一层的左右子树结点混在一起），只能按归属筛选。

以层序 ABCDEFG、中序 DBEAFCG 为例：层序首元素 A 是根，中序划出左 $\{D,B,E\}$、右 $\{F,C,G\}$；在层序剩余的 BCDEFG 里按序筛，属于左子树的是 BDE、属于右子树的是 CFG，各自作为新的层序序列递归下去。

筛完为什么仍是合法的层序序列：层序序列中同一棵子树内部的结点保持"层次由浅到深、同层从左到右"的相对次序；把不属于该子树的元素删掉，剩下的相对次序不变。

手算时更省事的说法是：在层序里，某棵子树中最先出现的那个结点就是这棵子树的根。 不必真的把整条子序列筛出来，每一步只要找到"层序中第一个落在当前中序区间里的元素"即可。

层序 + 中序的代码（要写代码时展开）

TreeNode* buildFromLevelIn(char level[], int ln,
                           char in[], int il, int ir) {
    if (ln == 0 || il > ir) return NULL;
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = level[0];                    // 层序首元素是根
    int k;
    for (k = il; k <= ir; k++)               // 在中序中定位根
        if (in[k] == level[0]) break;
    // 按"是否落在中序的根左侧"把层序剩余元素分成两组，组内保持原相对次序
    char leftLevel[ln], rightLevel[ln];
    int li = 0, ri = 0;
    for (int i = 1; i < ln; i++) {
        int inLeft = 0;
        for (int j = il; j < k; j++)
            if (level[i] == in[j]) { inLeft = 1; break; }
        if (inLeft) leftLevel[li++] = level[i];
        else        rightLevel[ri++] = level[i];
    }
    root->left  = buildFromLevelIn(leftLevel,  li, in, il,    k - 1);
    root->right = buildFromLevelIn(rightLevel, ri, in, k + 1, ir);
    return root;
}

内层那个 $j$ 循环是朴素的"判断元素是否属于左子树"，每次 $O(n)$；换成一个标记数组（先扫一遍中序左半段，把这些字符标记为"属左"）可降为 $O(1)$。

前序 + 后序为什么不行，以及它到底有几棵

前序 AB，后序 BA，下面两棵树都满足：

    树①            树②
     A              A
    /                \
   B                  B

前序：A B          前序：A B
后序：B A          后序：B A

两棵树不同（B 一个是左孩子、一个是右孩子），前序和后序却完全一样。根因：前序里 A 后面跟着 B，而"根之后先是左子树、再是右子树"——B 可以是左子树的全部，也可以是"左子树为空、右子树是 B"。后序同理。没有任何一条信息告诉我们左子树占了几个元素，而这正是中序的作用。

歧义的来源可以精确定位到一类结点：

给定一对合法的前序 + 后序序列，满足它们的二叉树共有 $2^k$ 棵，其中 $k$ 是度为 1 的结点个数。

论证分两半。度为 1 的结点各贡献一个自由的二选一：设结点 $N$ 只有一个孩子子树 $C$，把 $C$ 挂在左边时前序是 $N\cdot \mathrm{pre}(C)\cdot \epsilon$，挂在右边时是 $N\cdot \epsilon \cdot \mathrm{pre}(C)$——两者完全相同；后序同理。所以这个选择在两条序列上都不留痕迹。度为 0 和度为 2 的结点不贡献自由度：叶子没得选；度为 2 的结点两棵子树都非空，前序里"根之后先出现的那一段"必属左子树，边界被钉死。各结点的选择互相独立，故总数 $2^k$。

由 $2^k=1$ 得 $k=0$：前序 + 后序能唯一确定一棵二叉树，当且仅当树中不存在度为 1 的结点（每个结点要么是叶子、要么有两个孩子）。这类二叉树称为正则二叉树（也叫严格二叉树）。

注意与"满二叉树"的关系。 满二叉树一定不含度为 1 的结点，所以它是上述条件的特例——流传的说法"前序 + 后序只有对满二叉树才唯一"是充分不必要的。下面这棵不是满二叉树，但同样能被唯一确定：

        A
       / \
      B   E          前序：A B C D E
     / \             后序：C D B E A
    C   D            每个结点度为 0 或 2，k = 0 → 唯一

一句话记法：度为 1 的结点是唯一的歧义来源，有几个就翻几倍。

不过"不能唯一确定"不等于"什么都推不出来"。前序 + 后序仍然能定出层级关系，两条判据很好用：

• 去根后，前序首 $=$ 后序末 $⟺$ 根只有一个孩子（且那个孩子就是它）。若两者不等，前者是左子树的根、后者是右子树的根。
• 去根后两条序列完全逆序 $⟺$ 整棵树是一条单链（每个非叶结点都只有一个孩子）。因为一旦某个结点有两个孩子，左子树的结点在前序与后序里都排在右子树之前，相对方向一致，不会整体反转。

4 棵树的反例（想再看一组验证就展开）

前序 A B C、后序 C B A，满足的树有 4 棵：

   ①        ②        ③        ④
   A         A         A         A
  /         /           \         \
 B         B             B         B
/           \           /           \
C            C         C             C

四棵树互不相同，前序都是 ABC、后序都是 CBA。这里 A、B 都是度为 1 的结点，$k=2$，$2^2=4$ ✓

手算：不建树，直接推第三种序列

考场上通常不必真把树画出来，用"分段递归"直接推更快。以已知前序 ABDECFG + 中序 DBEAFCG，求后序为例：

前序 A | BDE | CFG          ← 首元素 A 是根，按中序分出左 3 个、右 3 个
中序 DBE | A | FCG
       ↓
   后序 = 后序(左) + 后序(右) + A

左：前序 B|D|E，中序 D|B|E → 后序(左) = D E B
右：前序 C|F|G，中序 F|C|G → 后序(右) = F G C

后序 = D E B  F G C  A = DEBFGCA

每一步都在做同一件事：把当前区间按根切成三块。 写成缩进的分段就不会串行，比画树快也不容易漏结点。做完用"后序末元素 $=$ 根"再核一遍。

不过有个例外：如果题目后面还要问"某结点在第几层""与谁同层""森林有几棵树"这类结构问题，就得老老实实把树画出来——分段法只给序列，不给形状。

三种组合的复杂度（想弄清时间空间结论时展开）

构造方式	时间复杂度	空间复杂度	来历
前序 + 中序（朴素）	$O(n^2)$	$O(n)$	每次在中序中线性查找根 $O(n)$，共 $n$ 次；最坏（单支树）递归 $n$ 层
前序 + 中序（预处理）	$O(n)$	$O(n)$	先用数组 / 散列表记下每个关键字在中序中的下标，定位降为 $O(1)$
后序 + 中序	同上	同上	完全对称
层序 + 中序（朴素）	最坏 $O(n^3)$	$O(n^2)$	每次筛选要对 $O(n)$ 个元素各做一次 $O(n)$ 的"是否属左"判断
层序 + 中序（用标记数组）	$O(n^2)$	$O(n)$	每层筛选降为 $O(n)$

为什么朴素版是 $O(n^2)$ 而不是 $O(n\log n)$：递归层数取决于树高，最坏是单支树的 $n$ 层；每层的"查找根"是 $O(n)$。平衡时确实是 $O(n\log n)$，但复杂度按最坏算。

考点速记

三条会被反复调用的结论：

1. 能否唯一确定，判据是"组合里有没有中序"：前序 / 后序 / 层序都只能定根，只有中序能把左右子树分开，两件事都办到才能还原。
2. 三步法的关键量是左子树结点数 $L$，它只能从中序里数出来。
3. 前序 + 后序的歧义全部来自度为 1 的结点，有 $k$ 个就有 $2^k$ 棵树；唯一的充要条件是 $k=0$（正则二叉树），满二叉树只是它的特例。

这一节在真题里被考过的形式（下方「真题练习」逐题对应）。值得先说一句：这一节的真题很少直接问"画出这棵树"，重建几乎总是中间步骤——五道里有三道，重建完之后还要再答一问。

• 给前序 + 后序，问能推出什么。 不建树，用上面那两条判据。一道问"根结点的孩子结点是谁"：去根后前序首 $=$ 后序末 $=$ e，所以根只有一个孩子 e。一道问"中序不可能是下列哪个"：先判定整棵树是单链，再枚举每条边挂左还是挂右（$n-1$ 条边共 $2^{n-1}$ 种），列出全部合法中序，不在其中的就是答案。枚举时记住：孩子挂左则中序里孩子在双亲之前，挂右则在双亲之后。
• 给中序 + 层序，重建后求后序。 层序在这里的作用是每一步指认子树的根——层序里最先出现的、落在当前中序区间内的结点就是该子树的根。这道题必须真的把树画出来。
• 重建之后再问森林的问题。 两道都是这个套路：一道给森林的先根 + 中根序列，要求对应二叉树的后序——先把森林遍历翻译成二叉树遍历（森林先根 ↔ 二叉树先序，森林中根 ↔ 二叉树中序），再由先序 + 中序重建，最后读后序。另一道给二叉树的先序 + 中序，问森林有几棵树——重建出二叉树后，数根的右链长度（根本身 + 沿右孩子能到达的所有结点数），那就是森林的棵数。这两条对应关系见 森林与二叉树的转换。

易错：把左子树结点数从前序或后序里估。 只能从中序里数。

易错：层序 + 中序时按位置切层序。 层序里左右子树交替出现，只能按归属筛。

易错：认为"前序 + 后序对满二叉树才唯一"。 充要条件是不存在度为 1 的结点，满二叉树只是特例。

易错：把森林的中根遍历对应成二叉树的后序。 它对应的是中序。

易错：数森林棵数时把右子树里的左孩子也算进右链。 只有沿右孩子链能到达的结点才算。

教材出处

• "若二叉树中各结点的值均不相同，任意一棵二叉树结点的先序序列、中序序列和后序序列都是唯一的"以及"由二叉树的先序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树"：严蔚敏《数据结构（C 语言版）》（第 2 版）印刷 p125（5.5.1 节第 2 部分"根据遍历序列确定二叉树"）
• "在先序序列中，第一个结点一定是二叉树的根结点"及随后由中序序列划分左右子树的论证，与由中序序列和后序序列确定二叉树的示例图：印刷 p125–p126
• 二叉树的递归定义与"二叉树的子树有左右之分，其次序不能任意颠倒"这一条，是中序具备划分能力、也是前序 + 后序产生歧义的前提：印刷 p113（5.2 节）

相关知识

前序遍历（首元素定根）｜中序遍历（提供左右划分，全篇的支点）｜后序遍历（末元素定根）｜层序遍历｜森林与二叉树的转换（重建题常见的外壳）｜树与二叉树基本概念（左右有别是歧义的源头）｜线索二叉树｜二叉排序树

相关文章

• 树与二叉树基本概念
• 前序遍历
• 中序遍历
• 后序遍历
• 层序遍历
• 线索二叉树
• 二叉排序树（BST）
• 平衡二叉树（AVL）
• 红黑树
• 哈夫曼树
• 堆（大根堆/小根堆）
• 并查集
• 树与森林
• 树与森林的转换

交互体验

前往完整可视化页面 →

真题练习

相关真题（5题）

2026Q32分2021Q42分2020Q42分2012Q32分2011Q52分