由遍历序列重构二叉树
看完你能亲手推导前序+中序如何唯一确定一棵二叉树，并说清什么组合做不到
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
由遍历序列重构二叉树
看完你能亲手推导前序+中序如何唯一确定一棵二叉树，并说清什么组合做不到
遍历序列回顾
上一页我们看到：光有一棵树的先序遍历，无法唯一还原树——就像只知道一家人的名单，画不出家谱。原因藏在这三个序列的定义里：根出现的位置不同，留下的线索也就不同。
刀落下的位置把蛋糕分成左右两块，对应根切分左右子树
一种序列为何不够
左右两棵树形状不同，但先序访问都是 A→B→C：同一序列对应多种结构。
核心原理：先序定根
上一页我们看到，单独一种遍历序列无法唯一确定一棵二叉树。但如果同时拿到两种序列呢？先序负责指认根，中序负责切分左右——两个角色分工配合，整棵树就能逐层还原。
先序负责每段队伍的排头（根），中序里排头左边的都归左队
重构五步流程
前序+中序两列序列，五步把每个节点钉回原位。
完整实例演练
用一个具体序列对完整走一遍递归切分过程
递归代码实现
从先序+中序重构二叉树的最小可运行实现，看清切分下标怎么算。
mid 同时是三把尺子：中序切左右、先序定根后切左右，两侧切片长度必须同为 mid，边界差一即错。
后序+中序：异同辨析
很多人背完先序版就混了：后序版到底哪里不同？其实只有一处。
- 根 = 先序序列第一个元素
- 在中序中找根，划分左右子树
- 递归重建，流程完全相同
- 根 = 后序序列最后一个元素
- 在中序中找根，划分左右子树
- 递归重建，流程完全相同
自测：序列重构
已知先序+中序序列可唯一重构二叉树。若把中序换成后序（先序+后序），结论如何？
先序+后序为何失效
中序能救场，是因为它把左右子树分了家。那先序+后序呢？两者都把根放在两端，中间全是孩子——听起来信息不少，可遇上只有一个孩子的节点，麻烦就来了。
知道每段有几个人，不等于知道谁站左边谁站右边
反例演示
同一对先序后序序列，能还原出两棵结构不同的树——这就是唯一性失效现场。
真二叉树：可重构条件
前面我们看到，先序+后序对普通二叉树会失效——某个节点只有一个孩子时，分不清它在左还是右。那什么时候这个组合才可靠？答案藏在一个特殊条件里：每个节点要么是叶子，要么恰有两个孩子。
只有双方各答一句（左右都有回应），位置才唯一确定
真二叉树重构流程
真二叉树下，先序+后序终于够用：首末匹配定根，余下元素对半分出左右子树。
要点收束
- ✓单独任一序列都丢信息，无法唯一定树
- ✓先序定根、中序分左右，配对即递归
- ✓后序+中序同理，只是根在序列末尾
- ✓先序+后序缺「独子归左还是右」的判断
- ✓真二叉树无独子，先序+后序即可重构
课后思考
先合上讲义自己想十分钟，再对照参考答案。
参考答案先序只告诉你根是谁，但根两侧各有多少节点、哪些属于左子树，只有中序能提供。没有这个切分点，递归第一步就卡住，子问题规模无法确定。
参考答案中序里根的左右各只剩一段，无法分出三个子树的边界。需要每个节点记录孩子数量，或改用「孩子数可区分的遍历序」才能切开。
参考答案不能随意放宽：只要存在度为1的节点，就无法判断它的唯一孩子挂在哪侧。真二叉树恰好消除了所有这类歧义，这已是该信息量下的边界。