NOIP 提高组初赛 · NOIP 2012 提高组初赛试题 第 15 题

一棵二叉树一共有 $19$ 个节点，其叶子节点可能有（ ）个。

别急着套公式，先想极端情况：一棵树最少几个叶子？最多几个？中间那些数字能不能凑出来？只要抓住"度为1的结点"和"度为2的结点"的关系，答案自然就跳出来了。

很多学生看到"19个结点"就下意识觉得叶子数大概在9或10左右，完全忘了"斜树"这种极端情况——所有结点都只有一个孩子，叶子数就是1。另外，有人会把"最多叶子"误算成11，以为n个结点最多有n/2个叶子，但这是完全二叉树在偶数结点时的特例，奇数结点时最多只有(n+1)/2，也就是10个。还有人会纠结为什么9个不行，其实只要构造一棵度为1的结点有1个、度为2的结点有9个的树，叶子数就是10；反过来，度为1的结点有11个、度为2的结点有7个，叶子数就是9，完全合法。

考点：二叉树叶子结点数的取值范围（1 ~ ceil(n/2)）。概念：二叉树里每个结点要么是叶子（度0），要么有一个孩子（度1），要么有两个孩子（度2）。设度1结点数为n1，度2结点数为n2，叶子数为n0，总节点n=n0+n1+n2。由二叉树性质n0=n2+1，代入得n=2n2+n1+1，所以n0=(n-1-n1)/2+1。因为n1≥0，所以n0≤(n+1)/2；又因为n1≤n-2（至少留两个位置给叶子和根），所以n0≥1。

命题视角：这道题故意给奇数19，就是想看你是否知道"最多叶子"是ceil(19/2)=10，而不是简单除以2。同时，它把1、9、10都列出来，就是要你明白中间值不是随便挑的，而是取决于度1结点的个数。

思考心法：拿到题先想极端。

• 最少叶子：让树尽量"斜"，n1取最大（n-2=17），则n0=(19-1-17)/2+1=1。所以A对。
• 最多叶子：让n1=0，n0=(19-1)/2+1=10。所以C对。
• 中间值9：需要n0=9，代入公式9=(19-1-n1)/2+1→n1=11。11个度1结点、7个度2结点、9个叶子，总节点19，完全合法。所以B也对。
• 为什么11不行？n0=11时，11=(19-1-n1)/2+1→n1=13，但13+11+12=36>19，不可能。所以D错。

避坑：别把"最多叶子"记成n/2，奇数时要向上取整；也别以为只要不是1和10的数就一定不行，9这种中间值完全可能。

考频与趋势：二叉树基础在题库共考过220题，覆盖8个级别。年度分布显示2023年20题、2024年60题、2025年67题、2026年28题，呈现爆发式增长，说明近年命题人越来越喜欢考这类"构造+极值"的灵活题，不再满足于死记硬背公式。分赛事看，GESP六级100题、七级56题、八级19题，NOIP提高组初赛9题，CSP提高级8题，都是高频考点。

预测：基于2024-2026年的数据，二叉树极值题（如"给定节点数，求叶子数范围"）在未来两年仍将是NOIP/CSP/GESP的必考题型，且很可能继续加大考查力度，甚至可能出现多问组合（如同时问叶子数、高度、路径数等）。暂无足够依据预测具体年份的题干形式，但"构造合法二叉树"的思维训练一定会持续出现。