Appearance
由遍历序列构造二叉树
为什么需要由遍历序列构造二叉树
一棵二叉树的遍历序列是"一维"的，而二叉树的结构是"二维"的。仅凭一种遍历序列无法唯一确定一棵二叉树——同一个前序序列可能对应多棵不同的树。
408 考研中，给定两种遍历序列还原二叉树是极高频考点，选择题、综合题均反复出现。掌握构造方法不仅能直接拿分，还能加深对遍历本质的理解。
核心结论：要唯一确定一棵二叉树，需要两种遍历序列，且其中必须包含中序遍历。
核心思想
所有构造方法都遵循同一个递归思路：
- 确定根节点：前序序列的第一个元素 / 后序序列的最后一个元素 / 层序序列的第一个元素就是当前子树的根。
- 划分左右子树：在中序序列中找到根节点的位置，其左侧为左子树的中序序列，右侧为右子树的中序序列。
- 递归构造：根据左右子树的节点数量，在前序/后序/层序序列中分离出左右子树各自的序列，递归重复上述过程。
为什么中序遍历不可或缺？ 因为只有中序遍历能提供"左右子树的划分依据"——根节点将中序序列一分为二。前序+后序的组合无法区分某个节点是左孩子还是右孩子（详见下文分析）。
交互可视化
通过下方的交互动画，你可以逐步观察由遍历序列构造二叉树的执行过程：
操作详解
前序 + 中序构造
原理：前序序列的第一个元素是根，在中序序列中定位该根，即可划分左右子树。
以前序 ABDECFG、中序 DBEAFCG 为例：
| 步骤 | 操作 | 前序序列 | 中序序列 | 确定的根 |
|---|---|---|---|---|
| 1 | 取前序首元素 A 为根，中序中 A 左侧 DBE 为左子树，FCG 为右子树 | A BDECFG | DBE A FCG | A |
| 2 | 左子树前序 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参考代码：
c
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; // 左子树节点数
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;
}后序 + 中序构造
原理：后序序列的最后一个元素是根，其余逻辑与前序+中序完全对称。
以后序 DEBFGCA、中序 DBEAFCG 为例：
| 步骤 | 操作 | 后序序列 | 中序序列 | 确定的根 |
|---|---|---|---|---|
| 1 | 取后序末元素 A 为根，中序划分为左 DBE、右 FCG | DEBFGCA | DBE A FCG | A |
| 2 | 左子树后序 DEB → 根为 B | DEB | D B E | B |
| 3 | 右子树后序 FGC → 根为 C | FGC | F C G | C |
构造结果与上例相同。
参考代码：
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;
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;
}层序 + 中序构造
原理：层序序列的第一个元素是根。在中序中定位根后划分左右子树，再从层序序列中按出现顺序分别提取属于左子树和右子树的元素，递归构造。
与前序/后序不同，层序序列中左右子树的元素是交替出现的，不能简单按位置切分，需要根据中序划分的结果来筛选。
以层序 ABCDEFG、中序 DBEAFCG 为例：
| 步骤 | 操作 | 层序序列 | 中序序列 |
|---|---|---|---|
| 1 | 层序首元素 A 为根，中序左 {D,B,E}，右 | A BCDEFG | DBE A FCG |
| 2 | 层序剩余 BCDEFG 中，属于左子树的按序为 BDE，属于右子树的为 CFG | — | — |
| 3 | 递归：左子树层序 BDE + 中序 DBE → 根 B；右子树层序 CFG + 中序 FCG → 根 C | — | — |
参考代码：
c
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;
}为什么前序 + 后序不能唯一确定二叉树
前序遍历顺序：根→左→右；后序遍历顺序：左→右→根。两者都能确定根节点，但都无法区分左右子树的边界。
当某个节点只有一个孩子时，仅凭前序+后序无法判断该孩子是左孩子还是右孩子。
反例：前序 AB，后序 BA，以下两棵树都满足：
A A
/ \
B B结论：前序+后序只有在二叉树是满二叉树（每个节点要么有 0 个孩子，要么有 2 个孩子）时才能唯一确定。
复杂度分析
| 构造方式 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 前序 + 中序 | O(n²) | O(n) | 每次在中序中查找根需 O(n)，共 n 层递归；用哈希表优化可达 O(n) |
| 后序 + 中序 | O(n²) | O(n) | 同上 |
| 层序 + 中序 | O(n²) | O(n) | 每层需筛选左右子树元素 |
空间复杂度：O(n)，递归调用栈深度最坏为 n（退化为链状树），平均 O(log n)。
考研高频考点
- ⭐ 给定前序+中序（或后序+中序）序列，画出二叉树（选择题/综合题极高频）
- ⭐ 判断哪些遍历序列组合能唯一确定二叉树（前序+中序✓、后序+中序✓、层序+中序✓、前序+后序✗）
- ⭐ 为什么前序+后序不能唯一确定二叉树（简答题/判断题常考）
- ⭐ 根据构造结果写出其他遍历序列（如给前序+中序，求后序/层序）
- 构造算法的递归实现思路（算法设计题偶尔考）
- 中序序列在构造过程中的划分作用（概念理解题）