Appearance
题目
要使一棵非空二叉树的先序序列与中序序列相同,其所有非叶节点须满足的条件是( )。
错因
A
把方向想反了。如果只有左子树,先序是 根, 左,中序是 左, 根——根的位置一前一后,序列必然不同。这种错往往出在没动笔画一个最小例子(一个父节点 + 一个左孩子)就直接选了。
C
度均为 1 的二叉树是一条"链",但链可以朝左也可以朝右:朝左不行,朝右才行。C 没区分方向,条件不充分——所以即使度都是 1,先序中序也未必相同。
D
度均为 2 意味着每个非叶节点同时有左孩子和右孩子。先序 根, 左子树, 右子树 永远会先访问根再访问左子树,而中序 左子树, 根, 右子树 必先访问左子树——两个序列首位元素不同,绝不可能相等。
总解析
把先序和中序写在一起对比:
| 顺序 | 访问规则 |
|---|---|
| 先序 | 根 → 左 → 右 |
| 中序 | 左 → 根 → 右 |
两者的差异点全在"根"和"左"的相对位置:先序先根后左,中序先左后根。要让它们逐位相同,唯一办法是让"左"消失——即每个非叶节点的左子树为空,只剩右子树。
这时两个序列都退化为:根 → 右 → 右 → ...,自然完全相同。
反过来:只要哪怕有一个节点存在左子树,那段子树就会让两个序列从此分叉。
最终答案是 B(只有右子树)。
直观例子:右斜链
1 → 2 → 3(1 的右是 2,2 的右是 3),先序1, 2, 3,中序也是1, 2, 3。换成左斜链立刻反例:先序1, 2, 3,中序3, 2, 1。