NOIP 普及组初赛 · NOIP 2010 普及组初赛试题 第 17 题

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

这题考二叉树遍历。先找根（前序首/后序尾），再在剩余序列里找左子树的根，最后数左子树节点数。

学生常把前序里紧跟根的第一个节点当成左子树全部节点，或误以为后序里根前所有节点都是左子树。其实左子树节点数不确定，得看左子树根在后序里的位置：左子树根在后序里出现的位置，决定了左子树包含哪些节点。

考点与概念

这道题考查二叉树的前序和后序遍历序列，要求推断根结点左子树的结点个数。

二叉树的遍历有三个核心序列：

• 前序：根→左子树→右子树（先访问根）；
• 中序：左子树→根→右子树（根在中间）；
• 后序：左子树→右子树→根（最后访问根）。

题目只给了前序和后序，没有中序，因此无法唯一确定整棵树，但根结点是确定的：前序第一个、后序最后一个都是根。本题根是A。

命题视角

命题人喜欢用“前序+后序”考“左子树大小不确定”这一陷阱。因为缺少中序，左子树可能很小（只有1~2个节点），也可能很大（几乎占满），右子树相应调整。考生必须意识到：左子树的大小不是固定的，要枚举所有可能。同时，命题人常把“左子树根”藏在后序序列的中间，让学生误以为“后序里根前面全是左子树”，从而选错。