NOIP 普及 2010 第一轮 第 17 题：由前序与后序遍历判断左子树规模

题目

一棵二叉树的前序遍历序列是 $\texttt{ABCDEFG}$，后序遍历序列是 $\texttt{CBFEGDA}$，则根结点的左子树的结点个数可能是（   ）。

选项

• A. 2
• B. 3
• C. 4
• D. 5

答案

A

题解

考点定位

利用前序、后序划分子树。

解题过程

前序为 ABCDEFG，后序为 CBFEGDA，根结点都是 A。

若左子树非空，它的根是前序中紧接 A 的 B。后序中 B 出现在第 2 位，因此该左子树的后序必须是 CB，包含 2 个结点；对应前序 BC。

剩余右子树的前序为 DEFG，后序为 FEGD，也能构造：D 的左子树为 E（E 的孩子为 F），右孩子为 G。再令 A 的左孩子为 B、B 的孩子为 C，即得到符合题意的一棵树。

所以左子树结点数可以是 2。

选 A。

易错提醒

前序、后序未必能唯一确定二叉树，但可以验证某个子树规模是否可能。截取子序列时不能漏掉 F。