NOIP 普及组初赛 · NOIP 2016 普及组初赛试题 第 22 题

约定二叉树的根节点高度为 $1$。一棵结点数为 $2016$ 的二叉树最少有（）个叶子结点；一棵结点数为 $2016$ 的二叉树最小的高度值是（ ）。

这题考二叉树形态极值：最少叶子看‘最瘦’（链状），最小高度看‘最胖’（完全二叉树）。拿到2016这个数，先想链状只有1个叶子；再想完全二叉树高度公式，算log₂2016取整加1，别被根高度为1的设定绕晕。

最容易栽跟头的地方有两个：一是把‘最少叶子’算成0，以为空树才是0叶子，但题目明确有2016个节点，链状树底端那个节点没孩子就是1个叶子，不可能为0；二是高度计算时把根高度当成0，或者直接用ceil(log₂n)而忘了公式是floor(log₂n)+1，导致算出10或12这种错误值。还有同学会纠结‘最少叶子’是不是要平衡树，其实题目只问最少，链状就是极限情况。

考点与概念

二叉树的形态千变万化，但两个极端情况是固定的： 1. 叶子最少：当树退化成一条直线（每个节点最多只有一个孩子）时，只有最底端那个节点没有孩子，叶子数=1。 2. 高度最小：当树尽可能‘满’时，即完全二叉树，高度最低。

命题视角

NOIP初赛喜欢考这种‘极值’问题，因为数字大（2016），没法画树，只能靠公式和逻辑推理。命题人通常会在‘根高度为1’这个细节上挖坑，很多学生习惯根高度从0算起，结果高度少算1。