Lab 04-T-06：由遍历序列构造二叉树理论题精练

目标

独立辨析由遍历序列构造二叉树中的核心概念、结构性质与遍历关系；
对选择题写出排除干扰项的依据，而不只记忆答案字母；
对源文档提供的综合题完成推导、算法设计或复杂度分析。

前置知识

建议先阅读第 4 章对应教材，再开始本组练习。

环境、输入与预期输出

环境：任意现代浏览器；综合题建议准备纸笔或本地编辑器。
输入：18 道四选一选择题，2 道综合题。
预期输出：一份独立作答记录，以及每道错题或综合题的完整推理过程。

作答方法

选择题先独立判断并记录依据，再点击“提交答案”；
提交后核对正确答案和解析，做错的题使用“重新作答”；
综合题先完成推导、伪代码或代码，再展开参考答案逐项核对；
对重复出现的真题，说明它在不同知识主题下分别考查了什么。

选择题

答题进度已答 0/18正确 0

第 1 题

难度★★★★考点由遍历序列构造二叉树、前序遍历、后序遍历、前序后序中序、单链二叉树、遍历推树

若一棵二叉树的前序遍历序列和后序遍历序列分别为 1,2,3,4 和 4,3,2,1，则该二叉树的中序遍历序列不会是()

1,2,3,4

2,3,4,1

3,2,4,1

4,3,2,1

第 2 题

难度★★★考点由遍历序列构造二叉树、前序遍历、后序遍历、前序+后序、二叉树重构、唯一性判断

若一棵二叉树的前序遍历序列为 a, e, b, d, c，后序遍历序列为 b, c, d, e, a，则根结点的孩子结点( )。

只有 e

有 e、b

有 e、c

无法确定

第 3 题

难度★★★★考点森林与二叉树的转换、由遍历序列构造二叉树、后序遍历、森林、二叉树、遍历转换、由先序中序构造

已知森林 $F$ 及与之对应的二叉树 $T$ ，若 $F$ 的先根遍历序列是 $a, b, c, d, e, f$ ，中根遍历序列是 $b, a, d, f, e, c$ ，则 $T$ 的后序遍历序列是( )。

b, a, d, f, e, c

b, d, f, e, c, a

b, f, e, d, c, a

f, e, d, c, b, a

第 4 题

难度★★★★考点森林与二叉树的转换、由遍历序列构造二叉树、树与森林、森林、二叉树转换、先序中序

某森林 F 对应的二叉树为 T , 若 T 的先序遍历序列是 a, b, d, c, e, g, f , 中序遍历序列是 b, d, a, e, g, c, f , 则 F 中树的棵数是( )。

第 5 题

难度★★★考点由遍历序列构造二叉树、层序遍历、后序遍历、二叉树重建、中序遍历

已知二叉树 T 的中序遍历为 b, e, d, f, c, a, g，层序遍历为 a, b, g, c, d, e, f，则其后序遍历序列为（）。

c, e, d, f, b, g, a

c, e, f, d, b, g, a

e, f, d, c, b, g, a

e, g, f, d, b, c, a

第 6 题

难度★★考点由遍历序列构造二叉树、二叉树构造、前序中序、根节点定位

已知一棵二叉树的前序遍历为 A, B, D, E, C，中序遍历为 D, B, E, A, C。该二叉树根结点的右孩子是( )。

第 7 题

难度★★★考点由遍历序列构造二叉树、二叉树构造、后序中序、子节点定位

已知一棵二叉树的后序遍历为 E, D, B, F, C, A，中序遍历为 E, B, D, A, F, C。求该二叉树根的左孩子的右孩子关键字是( )。

第 8 题

难度★★★考点由遍历序列构造二叉树、二叉树构造、层序中序、子树根定位

已知一棵二叉树的层序遍历为 A, B, C, D, E, F, G，中序遍历为 D, B, E, A, F, C, G。该二叉树左子树根的左孩子是( )。

第 9 题

难度★★★考点由遍历序列构造二叉树、二叉树构造、前序中序、父结点定位

已知一棵二叉树的前序遍历为 A, B, D, E, C, F, G，中序遍历为 D, B, E, A, F, C, G。求结点 E 的父结点是( )。

第 10 题

难度★★★考点由遍历序列构造二叉树、二叉树构造、前序中序、叶子计数

已知一棵二叉树的前序遍历为 A, B, D, C, E, F，中序遍历为 D, B, A, E, C, F。该二叉树的叶子结点个数是( )。

第 11 题

难度★★★★考点由遍历序列构造二叉树、二叉树构造、后序中序、树高度

已知一棵二叉树的后序遍历为 H, D, E, B, F, I, G, C, A，中序遍历为 H, D, B, E, A, C, F, G, I。该二叉树的高度是（根高度为 1）( )。

第 12 题

难度★★★★考点由遍历序列构造二叉树、二叉树构造、前序后序、唯一性、严格二叉树

关于仅由二叉树的前序遍历和后序遍历两个序列重建二叉树，下列描述正确的是（严格二叉树定义见 001 套首约定：每个非叶结点都恰好有 2 个孩子）( )。

任何二叉树都能由前序 + 后序唯一确定

仅当二叉树高度 ≤ 2 时才能由前序 + 后序唯一确定

仅当二叉树是严格二叉树时才能由前序 + 后序唯一确定

二叉树永远不能仅由前序 + 后序唯一确定

第 13 题

难度★★★★考点由遍历序列构造二叉树、二叉树构造、层序中序、多步定位

已知一棵二叉树的层序遍历为 A, B, C, D, E, F, G, H, I，中序遍历为 H, D, B, E, A, F, C, I, G。该二叉树右子树根的右孩子是( )。

第 14 题

难度★★★考点由遍历序列构造二叉树、二叉树构造、反向题、左斜链、遍历关系

一棵高度为 4 的二叉树是左斜链（每个非叶结点都只有左孩子、无右孩子）。关于该二叉树前序、中序、后序遍历序列的关系，下列描述正确的是( )。

前序和中序相同

前序和后序相同

中序和后序相同

前序、中序、后序三者完全相同

第 15 题

难度★★★★考点由遍历序列构造二叉树、二叉树构造、前序中序、度数统计

已知一棵二叉树的前序遍历为 A, B, C, D, E, F，中序遍历为 D, C, B, A, E, F。该二叉树中度为 1 的结点个数是( )。

第 16 题

难度★★★★考点由遍历序列构造二叉树、二叉树构造、前序中序、层序遍历输出

已知一棵二叉树的前序遍历为 A, B, D, C, E, F，中序遍历为 D, B, A, E, C, F。该二叉树的层序遍历结果是( )。

A, B, D, C, E, F

A, B, C, D, E, F

A, C, B, F, E, D

A, B, C, D, _, E, F

第 17 题

难度★★★★★考点由遍历序列构造二叉树、二叉树构造、综合判断、性质辨析

已知一棵二叉树的前序遍历为 A, B, D, E, C, F, G，中序遍历为 D, B, E, A, C, F, G。下列对该二叉树的描述中，错误的是( )。

该二叉树的高度为 4

该二叉树的叶子结点数为 3

该二叉树的后序遍历序列是 D, E, B, G, F, C, A

该二叉树是满二叉树

第 18 题

难度★★★考点由遍历序列构造二叉树、二叉树、先序遍历、后序遍历、单支树、树的高度

某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（　）。

空树或只有一个结点

高度等于其结点数

任意一个结点都无左孩子

任意一个结点都无右孩子

答案总览（建议完成全部题目后查看）

第 1 题：C
第 2 题：A
第 3 题：C
第 4 题：C
第 5 题：C
第 6 题：B
第 7 题：C
第 8 题：C
第 9 题：B
第 10 题：B
第 11 题：B
第 12 题：C
第 13 题：C
第 14 题：C
第 15 题：C
第 16 题：B
第 17 题：D
第 18 题：B

综合题

综合题 1｜巩固题

难度：★★★★ · 分值：12 分

考点：由遍历序列构造二叉树、二叉树、遍历序列构造、先序中序、后序遍历、分治、算法设计

已知一棵二叉树 $T$ 共 $n$ 个结点，结点值互不相同。给定 $T$ 的先序遍历序列 preorder[0..n-1] 和中序遍历序列 inorder[0..n-1]（保证两序列对应同一棵合法二叉树），请设计算法输出 $T$ 的后序遍历序列 postorder[0..n-1]。

(1) 给出算法的基本设计思想。

(2) 采用 C 语言描述算法，关键之处给出注释。

(3) 说明算法的时间复杂度与空间复杂度，并给出推导。

数据结构 / 接口约定（与 OJ wrapper 一致）：

/* 输入：先序数组 preorder[0..n-1]、中序数组 inorder[0..n-1]
 * 输出：后序数组 postorder[0..n-1]
 * 不需要显式构造 TreeNode；直接在数组上分治即可。
 */
void postorderFromPreIn(int *preorder, int *inorder, int n, int *postorder);

约束：

$1 \leq n \leq 1000$
所有结点值为 32 位有符号整数且两两不同
输入保证 preorder 与 inorder 对应同一棵合法二叉树（题目不要求做合法性校验）
时间复杂度允许 $O (n^{2})$ （408 大纲范围内的主流写法；解析中讨论 $O (n)$ 优化）
空间复杂度（不含输出数组本身）： $O (n)$ ，主要来自递归栈

测试覆盖维度：测试用例除常规情况外，还包含以下边界，WA 时建议逐个排查：

$n = 1$ ：单节点树，后序 = 先序 = 中序
左斜链树：每个非叶节点只有左孩子（如 pre = 1 2 3 4 5, in = 5 4 3 2 1），后序 = 5 4 3 2 1
右斜链树：每个非叶节点只有右孩子（如 pre = 1 2 3 4 5, in = 1 2 3 4 5），后序 = 5 4 3 2 1
完全二叉树：左右子树同高，验证递归在两侧均推进
含负数 / 大跨度整数值：验证比较是按值不按位置
较大规模（ $n$ 接近 $1000$ 的链状树）：验证算法的渐近复杂度未爆 + 递归栈未溢

参考答案与详细解析

详细解析

思路分析

先序遍历的访问顺序是"根→左子树→右子树"，中序遍历的访问顺序是"左子树→根→右子树"。两个特性叠加产生一个唯一性结论：先序的首元一定是当前子树的根；用这个根在中序里定位，左侧落在左子树、右侧落在右子树，且左右子树的规模也随之确定。一旦左右子树范围明确，递归就能继续分解。

记**" $T$ 的后序 = (左子树后序) ++ (右子树后序) ++ (根)"**。沿这条结构性等式自顶向下分治，把后序数组一段一段填好即可。

解法 1（408 大纲范围内的主流写法）：递归 + 中序线性扫描定位根， $O (n^{2})$

记当前子树在先序中的下标范围是 $[p l, p r]$ 、在中序中是 $[i l, i r]$ 。

子问题：build(pl, pr, il, ir, postBase)
递归基： $p l > p r$ （即 $i l > i r$ ）—— 空子树，什么都不做
一般步骤：
1. 取根：root = preorder[pl]（先序首元）
2. 中序定位：从 inorder[il..ir] 中线性扫描找到 root，记下标 k
3. 算左子树规模：leftSize = k - il
4. 递归左子树：先序段为 [pl+1, pl+leftSize]、中序段为 [il, k-1]，结果写入后序数组前 leftSize 个位置
5. 递归右子树：先序段为 [pl+leftSize+1, pr]、中序段为 [k+1, ir]，结果写入后序数组紧接的位置
6. 回填根：把根写到当前子树后序段的最末位

为什么先序首元就是根（命题人复盘）：先序定义里"先访问根，再递归子树"——访问顺序的第一项即为当前调用栈最顶层那个根。当前子树先序段的首元就是这层"先访问"的产物。

为什么中序里左根右的规模能拆出左右子树（命题人复盘）：中序的相对顺序是"左子树的所有节点 → 根 → 右子树的所有节点"。把根 root 在中序里的下标 k 找到后，[il, k-1] 就整段属于左子树、[k+1, ir] 就整段属于右子树——这两段在中序里恰好就是各自子树的中序遍历，规模 leftSize = k - il、rightSize = ir - k 因而精确。

为什么先序也能配套拆（命题人复盘）：先序里"根→左子树先序→右子树先序"，根占位 1，左子树占接下来连续 leftSize 位，右子树占剩下 rightSize 位——切点完全由中序定出的 leftSize 决定。

解法 2（讨论性优化）：递归 + 中序哈希定位根， $O (n)$

每次在中序里找根要扫一遍 [il, ir]，链状二叉树（左斜 / 右斜）会让总扫描次数达到 $Θ (n^{2})$ 。优化方案：预处理一个 pos[v] = i 的反查表，使得"在中序里找根" $O (1)$ 完成；总时间降到 $O (n)$ ，空间多 $O (n)$ 。

维度	解法 1 线性扫描	解法 2 哈希定位
时间	最坏 $O (n^{2})$ ，平均 $O (n \log n)$	$O (n)$
空间（除输出和递归栈）	$O (1)$	$O (n)$ （反查表）
大纲适配	✅ 408 主流，C 语言纯数组实现	⚠️ 反查表通常配合 `map`/`unordered_map`，超出 408 大纲；若用裸数组下标作 key，需值域已知或额外离散化
推荐场景	大题作答	工程实现 / 大规模数据

下方参考实现给出解法 1：408 大题的标程基线、纯 C / 不依赖任何容器、可读性优先。

参考实现（C）

/* 在中序的 [il, ir] 段里线性查找 root 的下标；调用方保证一定能找到。 */
static int locateInInorder(const int *inorder, int il, int ir, int root) {
    for (int i = il; i <= ir; i++) {
        if (inorder[i] == root) return i;
    }
    return -1;  /* 不可达：题面已约定 preorder 与 inorder 一致 */
}

/* 在 preorder[pl..pr] / inorder[il..ir] 上分治，把当前子树的后序写到 postorder[pob..pob+len-1] */
static void build(const int *preorder, const int *inorder,
                  int pl, int pr, int il, int ir,
                  int *postorder, int pob) {
    if (pl > pr) return;                                    /* 空子树 */
    int root = preorder[pl];                                /* ① 先序首元 = 根 */
    int k = locateInInorder(inorder, il, ir, root);         /* ② 中序定位根 */
    int leftSize = k - il;                                  /* ③ 左子树规模 */
    int rightSize = ir - k;                                 /* ④ 右子树规模 */

    /* ⑤ 递归左子树：后序写入当前段的前 leftSize 个位置 */
    build(preorder, inorder,
          pl + 1, pl + leftSize,
          il, k - 1,
          postorder, pob);

    /* ⑥ 递归右子树：后序紧接其后写入 rightSize 个位置 */
    build(preorder, inorder,
          pl + leftSize + 1, pr,
          k + 1, ir,
          postorder, pob + leftSize);

    /* ⑦ 回填根：当前子树后序的最末一位 */
    postorder[pob + leftSize + rightSize] = root;
}

void postorderFromPreIn(int *preorder, int *inorder, int n, int *postorder) {
    if (n <= 0) return;
    build(preorder, inorder, 0, n - 1, 0, n - 1, postorder, 0);
}

关键点说明：

下标段必须三组同步推进：preorder 段、inorder 段、postorder 写入起点三者任何一处算错 leftSize / rightSize，整棵树后续构造就错位 → 输出乱序。建议在草稿上画 pl / pr / il / ir / pob 五个变量的位置图再写代码。
递归基用 pl > pr 而非 pl >= pr：单节点子树 pl == pr，仍需写入后序——若用 pl >= pr 直接返回，叶子节点会被漏掉。
postorder 的写入位置由"当前子树后序段的起点"递推：左子树起点 = 父段起点 pob，右子树起点 = pob + leftSize，根填在 pob + leftSize + rightSize。这三个位置在后序段里依次排列，正好对应"左 ++ 右 ++ 根"。

复杂度证明

时间复杂度 $O (n^{2})$ ：

每次递归调用做两件工作：

在中序 [il, ir] 中线性扫描定位根 —— 至多 $O (i r - i l + 1)$ 即 $O (m)$ ，其中 $m$ 是当前子树大小；
后序填根一次 —— $O (1)$ 。

设 $T (m)$ 为大小为 $m$ 的子树的总耗时，则有：

T (m) = T (m_{L}) + T (m_{R}) + m

其中 $m_{L} + m_{R} = m - 1$ 。

最坏情形（左/右斜链）：每次划分 $m_{L} = m - 1, m_{R} = 0$ （或对称），递推式 $T (n) = T (n - 1) + n$ ，解得 $T (n) = Θ (n^{2})$ 。
最好/平均情形（划分均衡）： $T (n) = 2 T (n / 2) + n$ ，由主定理得 $T (n) = Θ (n \log n)$ 。

综合最坏情形给出 $O (n^{2})$ 上界。题面 $n \leq 1000$ ，最坏 $10^{6}$ 量级运算，远在时限内。

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

递归栈：递归树的深度 = 二叉树的高度 $h$ 。最坏（链状） $h = n$ ，每帧常数大小（参数 5–6 个 int + 返回地址），合计 $O (n)$ ；
不使用 malloc、不开辅助数组，除输入输出外无额外堆开销。

综合： $S (n) = O (h) = O (n)$ （最坏）， $O (\log n)$ （平均，平衡情形）。

易错点

写在最前：本题最大的认知陷阱不在"如何写代码"，而在**"分治的三组下标段如何同步推进"。题面给的输入只有"两段数组"，但递归时每一层都要维护先序段、中序段、后序写入起点**三组下标——任一处算错，整棵后序错位。下面 5 个盲区按"从混淆遍历语义 → 边界 off-by-one → 复杂度认知"的层次依次展开。

盲区 A：「先序首元 vs 后序末元的混淆」（语义层，跨题元层共用术语）
一战考生看到"输出后序"会潜意识联想"后序末元是根"——这话本身对，但输入并没有给后序，根只能从先序首元取。考生混淆后会写出"postorder[pr] 是根"试图反推——此时 postorder 还没填好，读出来是垃圾值。
错误推演：第一层 n = 5，考生从尚未填写的 postorder[4] 取根（脏数据，比如 0），跑去中序里找 0，找不到，分治崩。
正解：给什么用什么。输入只有先序+中序，根从先序首元取（每层递归的 preorder[pl]）；后序是写的方向，不是读的方向。本盲区命名为「遍历首末位语义混读」，与 ds-2011-05 / ds-2012-03 等选择题对"先序首元 = 根 / 后序末元 = 根"的对偶考察是同源——但单一遍历无法定位左右子树规模，必须配合中序。
盲区 B：「递归区间端点漂移」（算法层，写一行就翻车）
考生记不清递归调用应该传 pl+1, pl+leftSize 还是 pl+1, pl+leftSize-1。
错误推演（端点 +1 漂移）：考生写成 build(pl+1, pl+leftSize-1, ...)，等价于把左子树先序段右端点向左移一位——最右那位（属于左子树的"右子树根"）被丢掉。
- 具体例子：pre = 1 2 3, in = 2 1 3，正确左子树先序段 [1, 1]（只有节点 2），右子树先序段 [2, 2]（只有节点 3）。若错写成 [1, 0]，左子树成空树，递归立刻退出；节点 2 永远不会被写入后序。最终输出仅含 1 和 3，节点 2 丢失。
正解：左子树先序段是 [pl+1, pl+leftSize]——pl 是根，根后面紧跟 leftSize 个节点是左子树的先序遍历，所以右端点 = pl + leftSize（不减 1）。同理右子树先序段是 [pl+leftSize+1, pr]。本盲区命名为「递归区间端点漂移」，是所有分治题（归并 / 快排 / 二分 / 线段树）共用的元层错因，跨题主动回扣。
盲区 C：「中序定位根的搜索范围越界」（算法层）
考生在中序里找根时，直接 for (int i = 0; i < n; i++) 而不是 for (int i = il; i <= ir; i++)——也就是在整个中序数组里找而不是在当前子树对应的中序段里找。
错误推演：本题题面已保证"节点值互不相同"，所以即便在整段里找也能找到正确的 k，这种写法在本题居然能 AC。但这只是"题面恰好保护了你"，一旦下一道题放开"节点值可重复"的约束（如 408 真题 ds-2026-03 选择题就考"重复值时构造是否唯一"的判定），同样写法立刻错——会在其他子树里命中同名节点，左右子树规模算错。
- 推演（假想 in = 1 2 1 重复值）：找节点 1 时整段扫描会先命中下标 0，但真实根在下标 2，整棵树构造错位。
正解：严格在 [il, ir] 里找——这是分治不变量的一部分。即便本题"碰巧能 AC 的偷懒写法"也不要采用：写代码时让"当前子树范围"成为搜索的硬边界，习惯比性能更重要。本盲区命名为「分治不变量越界」，与"二分查找写出 mid 后边界不收紧"是同源。
盲区 D：「后序写入位置算错」（算法层，最隐蔽）
考生把后序填根的位置写成了"绝对下标 pr"（也就是当前先序段右端点），看起来"后序末位 = 根"挺合理，跑小样例也能过——但它假设后序段和先序段在数组里下标相同，这只在最顶层一次调用时成立，递归到子树就不再成立。
错误推演：pre = 1 2 3, in = 2 1 3。
- 顶层 pl=0, pr=2, il=0, ir=2, pob=0，根 1 应写到 postorder[2]。考生写 postorder[pr] 即 postorder[2] —— 巧合对了。
- 左子树递归 pl=1, pr=1, il=0, ir=0, pob=0，根 2 应写到 postorder[0]（左子树后序段的最末位 = 起点 + 子树大小 - 1 = 0 + 1 - 1 = 0）。考生写 postorder[pr] 即 postorder[1] —— 错了！正确位置 postorder[0] 被空着，错误位置 postorder[1] 被覆写。
- 最终输出 _ 2 1（首位是脏数据），WA。
正解：后序写入位置由 pob（当前子树后序段的起点）+ 当前子树大小 - 1 推出。代码里写成 postorder[pob + leftSize + rightSize] = root —— leftSize + rightSize 就是当前子树除根外的节点数，加到起点上正好是根在后序段的位置。永远不要用先序/中序段的下标去寻址后序数组，三组下标段是各自独立的。本盲区命名为「分治区间映射错位」，与归并排序"合并时取自 aux[] 但写到 arr[]"是同源。
盲区 E：「链状二叉树递归栈深没意识」（元层-复杂度认知）
考生写完递归看到题面 $n \leq 1000$ ，觉得"递归栈 $O (\log n)$ 才 10 层左右，完全 OK"。
错误推演：左斜链（pre = 1 2 3 ... 1000, in = 1000 999 ... 1）的递归深度等于树高 = 1000，不是 $\log n$ 。默认线程栈通常 1 MB，每帧约 64–128 字节，1000 层栈深约 100 KB，本题恰好仍安全；但若 $n$ 放到 $10^{5}$ 量级，扁平栈帧 100 层 × 1 MB = 直接爆栈。考生背"递归 $O (\log n)$ "是把"平衡二叉树场景的最好情形"当成了普适规律。
正解：递归深度 = 当前数据的实际树高 $h$ ，不是 $\log n$ 。链状二叉树 $h = n$ ，平均随机树 $h = O (\sqrt{n})$ ，平衡树 $h = O (\log n)$ 。本题 $n \leq 1000$ 在常规栈下安全（OJ 主流 1–8 MB 栈），但做更大规模题时应改写为显式栈迭代，或预先分析最坏树形。本盲区命名为「链式递归吞栈」，与 [[general-tree]] 题"孩子兄弟链表的兄弟链递归"是同源——所有"链表化结构"的递归都隐含线性栈深风险。

综合题 2｜巩固题

难度：★★★ · 分值：12 分

考点：由遍历序列构造二叉树、二叉树、遍历序列构造、先序中序、唯一性证明、演算

已知一棵二叉树 $T$ 共 6 个结点，结点互不相同，其先序遍历序列与中序遍历序列分别为：

\begin{aligned} preorder & = A, B, D, E, C, F \\ inorder & = D, B, E, A, F, C \end{aligned}

请完成以下任务：

(1) 手工演算给出递归构造 $T$ 的逐层分块过程：在每一层中，圈出"当前子树的根"，写出"先序对应位置"与"中序左/右子段"，并标出递归到子问题的规模。

(2) 用 binary-tree fence 画出最终的二叉树 $T$ ，并写出其后序遍历序列。

(3) 证明："先序遍历 + 中序遍历"为何能唯一确定一棵二叉树（且结点值互不相同）。要求给出递归奠基与递归步两段。

本套统一约定：
二叉树结点高度从 1 起算，空子树高度 0
先序 = 根 → 左子树 → 右子树；中序 = 左子树 → 根 → 右子树；后序 = 左子树 → 右子树 → 根
本题保证两序列对应同一棵合法二叉树且结点值两两不同
"前缀 / 后缀长度" 与 "子段范围" 全程采用闭区间 $[l, r]$ 表述

参考答案与详细解析

详细解析

思路分析（演算过程拆 Step）

算法骨架（先回顾再演算）

由"先序首元 = 当前子树的根"+"中序里根的位置切出左右子树"两条性质递归到底——

在先序 pre[pl..pr] 中取首元 pre[pl] 作为根 $r$
在中序 in[il..ir] 中线性扫描定位 $r$ 的下标 $k$ ，则中序左子段 in[il..k-1]、右子段 in[k+1..ir]
左子树规模 leftSize = k - il，先序左子段 pre[pl+1 .. pl+leftSize]、先序右子段 pre[pl+leftSize+1 .. pr]
在两侧子段上递归；递归基为 pl > pr（空子树）

下面在本题数据上把每一层分块过程画出来。

Step 1: 顶层（整棵树）

preorder index:   0 1 2 3 4 5
preorder:         A B D E C F      ← 取首元 A 作为根
                  ^
inorder  index:   0 1 2 3 4 5
inorder:          D B E A F C      ← 在中序里找 A，位置 k = 3
                        ^

切分：

段	范围	内容	规模
左子树先序	`pre[1..3]`	`B D E`	3
左子树中序	`in[0..2]`	`D B E`	3
右子树先序	`pre[4..5]`	`C F`	2
右子树中序	`in[4..5]`	`F C`	2

核心数值复核（条 26 二次验算）：左子树规模 leftSize = k - il = 3 - 0 = 3；右子树规模 rightSize = ir - k = 5 - 3 = 2；两者之和 5 = 总规模 6 − 1（根占 1 位），自洽 ✓

Step 2: 递归到左子树 pre = B D E, in = D B E

preorder index:   0 1 2
preorder:         B D E             ← 取首元 B 作为左子树的根
                  ^
inorder  index:   0 1 2
inorder:          D B E             ← B 在中序中位置 k = 1
                    ^

切分：

段	范围	内容	规模
左子树先序	`pre[1..1]`	`D`	1
左子树中序	`in[0..0]`	`D`	1
右子树先序	`pre[2..2]`	`E`	1
右子树中序	`in[2..2]`	`E`	1

数值复核：leftSize = 1 - 0 = 1、rightSize = 2 - 1 = 1，1 + 1 = 2 = 3 − 1 ✓

Step 3: 左子树的两个孩子（单节点子树）

子段 pre = D, in = D：取 D 作根；左右子段都是空（递归基 pl > pr），D 是叶子
子段 pre = E, in = E：取 E 作根；E 是叶子

左子树最终形态：

text

B(D, E)

Step 4: 递归到右子树 pre = C F, in = F C

preorder index:   0 1
preorder:         C F               ← 取首元 C 作为右子树的根
                  ^
inorder  index:   0 1
inorder:          F C               ← C 在中序中位置 k = 1
                    ^

切分：

段	范围	内容	规模
左子树先序	`pre[1..1]`	`F`	1
左子树中序	`in[0..0]`	`F`	1
右子树先序	`pre[2..1]`	（空）	0
右子树中序	`in[2..1]`	（空）	0

数值复核：leftSize = 1 - 0 = 1、rightSize = 1 - 1 = 0，1 + 0 = 1 = 2 − 1 ✓；右子段 pre[2..1] 满足 pl > pr → 空树。

Step 5: 右子树的孩子

子段 pre = F, in = F：取 F 作根；左右皆空，F 是 C 的左孩子；C 的右子树为空

右子树最终形态：

text

C(F, _)

Step 6: 合并整棵树

把 Step 3、Step 5 的结果挂回根 A：

text

A(B(D, E), C(F, _))

最终答案

(2) 最终二叉树形态与后序遍历

二叉树 $T$ （高度 3，共 6 结点）：

text

A(B(D, E), C(F, _))

按"左子树后序 → 右子树后序 → 根"递归拼出 $T$ 的后序：

$T$ 的左子树（根 B）后序 = D E B（D、E 都是叶子）
$T$ 的右子树（根 C）后序 = F C（F 是 C 的左孩子；C 右子树空）
$T$ 的后序 = $(D, E, B) \oplus (F, C) \oplus (A) = D, E, B, F, C, A$

关键数值二次验算（条 26）：直接在 Step 6 的树上跑一遍后序遍历——

visit(A):
  visit(B):
    visit(D): 输出 D
    visit(E): 输出 E
    输出 B
  visit(C):
    visit(F): 输出 F
    输出 C
  输出 A

逐项输出顺序：D, E, B, F, C, A ✓ 与递归拼接得到的结果一致。

postorder = D, E, B, F, C, A

(3) 唯一性证明：先序 + 中序 → 二叉树唯一

命题：设二叉树 $T$ 的结点值两两不同。给定 $T$ 的先序序列 $P = p_{1} p_{2} \dots p_{n}$ 与中序序列 $I = i_{1} i_{2} \dots i_{n}$ ，则 $T$ 由 $(P, I)$ 唯一确定。

证明（对结点数 $n$ 作归纳）

奠基 $n = 0$ 与 $n = 1$ ：

$n = 0$ ： $P = I = ()$ 是空序列，唯一对应空树。
$n = 1$ ： $P = I = (v)$ ，唯一对应单结点树 {v}，左右子树皆空。

归纳步 $n \geq 2$ ：

假设对任意结点数 $< n$ 的"先序 + 中序"对，归纳假设成立——即每个这样的对唯一确定一棵二叉树。现在证 $n$ 个结点时也唯一。

根唯一：先序的定义为"根 → 左子树先序 → 右子树先序"，所以 $p_{1}$ 必是 $T$ 的根。结点值互不相同这一约束保证 $p_{1}$ 不与任何子树中的值冲突，根的身份不被歧义化。
左右子树规模唯一：在中序里找到 $p_{1}$ 的位置——由"值互不相同" $p_{1}$ 在 $I$ 中恰好出现一次，记其下标为 $k$ （即 $i_{k + 1} = p_{1}$ ，从 1 起）。中序的定义为"左子树中序 → 根 → 右子树中序"，所以：
- $T$ 的左子树中序 $= i_{1} i_{2} \dots i_{k}$ ，规模 $L = k$
- $T$ 的右子树中序 $= i_{k + 2} \dots i_{n}$ ，规模 $R = n - 1 - k$
- 显然 $L + R = n - 1$ 。
左右子树先序唯一：先序的"根 → 左子树先序 → 右子树先序"结构、加上左子树规模 $L$ ，立刻得：
- $T$ 的左子树先序 $= p_{2} p_{3} \dots p_{L + 1}$ （紧跟根之后的 $L$ 项）
- $T$ 的右子树先序 $= p_{L + 2} \dots p_{n}$ （剩余 $R$ 项）
子问题严格变小：左子树规模 $L \leq n - 1 < n$ ，右子树规模 $R \leq n - 1 < n$ 。
归纳假设兜底：由归纳假设， $T$ 的左、右子树作为"先序 + 中序"对各自唯一确定。

把根 $p_{1}$ 、唯一的左子树与唯一的右子树挂在一起，得到唯一的 $T$ 。 $◼$

为什么"值互不相同"是必要条件：若允许重复值，第 2 步"在中序中找根的位置"会出现多个候选，左右子树规模不唯一——直接反例 pre = 1 1, in = 1 1，可对应"根 1，右孩子 1"或"根 1，左孩子 1"两种合法形态，先序与中序完全相同。本套约定"结点互不相同"正是为了让构造唯一。

与"后序 + 中序"的对偶：用完全对称的论证可证"后序 + 中序"也唯一确定二叉树（后序最末元 = 根，中序仍负责切左右子段）。但"先序 + 后序"无法唯一确定——因为两序列都不能划分左右子树范围（必须借助中序），故反例众多。这是 408 考研 KP tree-construction 在选择题里反复点过的盲区（参见 ds-2011-05）。

易错点

盲区 A：「中序左右子段长度数错」（算法层）
Step 1 中考生在中序里找到 A 的位置 k = 3，常错把"左子段长度"算成 k（含根的位置）而不是 k - il。
- 错误推演：若错认为"左子段 = in[0..3] 长度 4"，则左子段会把 A 自己也算进去；先序左子段对应规模也变成 4，把 pre[1..4] = B D E C 全部当左子树——C 实际是右子树的根，整棵右子树丢失。
- 正解共识：leftSize = k - il（不含根，左子段是 in[il..k-1]），rightSize = ir - k。本盲区命名为「左右子段长度漂移」，与 kp-tree-construction-101 盲区 B「递归区间端点漂移」是同源——都源于"包不包含根"的边界把控。
盲区 B：「先序左子树长度 = 自定，而非中序定」（算法层）
一战考生常在 Step 1 凭直觉拍脑袋"先序里 A 之后的前一半是左子树、后一半是右子树"——忽略了"先序里左右子树规模无法独立确定，必须靠中序切"。
- 错误推演：在本题中"凭直觉切一半"恰好是 pre[1..3] = B D E 作左、pre[4..5] = C F 作右，碰巧正确，但这是侥幸。改成 preorder = A B C D E F, inorder = B A D C E F（左子树仅 1 节点 B、右子树 4 节点 D C E F）就立刻翻车——"凭直觉一半一半"会把左子树扩成 B C，错误地把 C 也吞进左子树。
- 正解共识：先序的切点完全由中序提供的 leftSize 决定——先序里"根之后紧跟连续 leftSize 项是左子树先序，剩下是右子树先序"，这个"连续 leftSize 项"不是凭直觉而是凭中序里根左边的字符数。本盲区命名为「先序自切幻觉」，跨题与 kp-tree-construction-101 盲区 A「遍历首末位语义混读」同根——都源于"误以为单一遍历可以独自完成切分"。
盲区 C：「唯一性证明缺归纳基（空树 / 单节点）」（元层 - 正确性认知）
写到 (3) 唯一性证明时，考生常常只写归纳步"根唯一、左右子树规模唯一、递归到子问题"就收笔，忘了写 $n = 0$ 与 $n = 1$ 的奠基。
- 错误推演：归纳法证明若无奠基，递归会"无限下溯"——递归到 $n = 1$ 时仍要"再切左右子树"，但 $n = 1$ 时左右子段都是空序列，必须由 $n = 0$ 奠基承接"空序列 → 空树"才能终止。缺奠基的证明逻辑链断裂，408 阅卷会按"证明残缺"扣分。
- 正解共识：归纳法的两件套缺一不可——"奠基（基础情形 $n = 0$ 或 $n = 1$ 直接判定）+ 归纳步（假设 $< n$ 成立、证 $n$ 成立）"。本盲区命名为「归纳法奠基缺失」，跨题与 kp-merge-sort 「合并排序正确性证明」、kp-binary-search "二分边界证明"等所有递归式 / 分治式正确性证明同源——都是"只写递推规则、忘了写终止条件 / 边界情形"的高频元层错。
盲区 D：「先序 + 后序也能唯一确定」（元层 - 概念混淆）
有考生看完"先序 + 中序唯一"就想当然地外推："那先序 + 后序应该也能唯一吧？"
- 错误推演：考虑两棵不同的二叉树——树 1：根 1，左孩子 2（无右孩子）；树 2：根 1，右孩子 2（无左孩子）。
  - 树 1：先序 1 2，后序 2 1
  - 树 2：先序 1 2，后序 2 1
  - 两棵不同的树先序后序完全相同！原因：先序"根之后是左子树先序还是右子树先序"无法判别；后序"最末元之前是左子树后序还是右子树后序"也无法判别——少了中序提供的"左右切点"。
- 正解共识："先序 + 中序" / "后序 + 中序" → 唯一；"先序 + 后序" → 不唯一（除非每个内部结点都有两个孩子，即满二叉树时唯一）。本盲区命名为「遍历对组合幻觉」，跨题与 ds-2011-05 选择题 C 选项是同一考察轴——选择题里点过，大题里同样要会答。
盲区 E：「在整段中序里找根而不是在子段里找」（算法层 / 元层 - 数据结构本质认知）
Step 2 递归到左子树时，考生若不维护"当前子段范围 [il, ir]"，直接在整段中序里找根，会因"结点值互不相同"侥幸找对位置；但一旦理解错"分治不变量"，下游会反复犯类似越界错。
- 错误推演：本题里"值互不相同"让"整段扫描"也能命中正确位置——但这种"碰巧能对"的写法会麻痹一战考生。若题目把约束改为"含重复值的二叉树"，整段扫描会先命中别的子树里的同名值，左右子树规模算错，构造立刻歪。
- 正解共识：搜索范围严格收紧到当前子段 [il, ir]——这是分治"不变量收紧"的标准要求。本盲区命名为「分治不变量越界」，与 kp-tree-construction-101 盲区 C「分治不变量越界」同名共用——大题里"画演算"时务必显式标注"在 in[il..ir] 子段里找"。

完成清单

18 道选择题均已独立作答，错题能说明其余选项为何不成立；
2 道综合题均已独立完成，并在展开解析前写出推导或算法；
能把本组题目涉及的关键性质、遍历顺序或算法复杂度说清楚；
已记录仍需回到教材复习的知识点。

复盘

哪道题最容易因遍历顺序、层次口径或结构关系判断失误？
我能否不用背答案，重新画树或写出访问过程？
如果题目改变一个条件，原结论是否仍成立？

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

目标 ​

前置知识 ​

环境、输入与预期输出 ​

作答方法 ​

选择题 ​

综合题 ​

综合题 1｜巩固题 ​

思路分析 ​

解法 1（408 大纲范围内的主流写法）：递归 + 中序线性扫描定位根，O(n2) ​

解法 2（讨论性优化）：递归 + 中序哈希定位根，O(n) ​

参考实现（C） ​

复杂度证明 ​

易错点 ​

综合题 2｜巩固题 ​

思路分析（演算过程拆 Step） ​

算法骨架（先回顾再演算） ​

最终答案 ​

(2) 最终二叉树形态与后序遍历 ​

(3) 唯一性证明：先序 + 中序 → 二叉树唯一 ​

易错点 ​

完成清单 ​

复盘 ​

目标

前置知识

环境、输入与预期输出

作答方法

选择题

综合题

综合题 1｜巩固题

思路分析

解法 1（408 大纲范围内的主流写法）：递归 + 中序线性扫描定位根， $O (n^{2})$

解法 2（讨论性优化）：递归 + 中序哈希定位根， $O (n)$

参考实现（C）

复杂度证明

易错点

综合题 2｜巩固题

思路分析（演算过程拆 Step）

算法骨架（先回顾再演算）

最终答案

(2) 最终二叉树形态与后序遍历

(3) 唯一性证明：先序 + 中序 → 二叉树唯一

易错点

完成清单

复盘