NOIP 普及 2011 第一轮 第 7 题：给定叶结点数的二叉树最小深度

题目

如果根结点的深度记为 $1$，则一棵恰有 $2011$ 个叶结点的二叉树的深度最少是（   ）。

选项

• A. 10
• B. 11
• C. 12
• D. 13

答案

C

题解

考点定位

本题考「二叉树高度下界」,对应大纲 3.2.2 二叉树（难度【2】）。

解题过程

高度 h 的二叉树最多 2^(h−1) 个叶子（第 h 层满）。2011 个叶子：

$$2^{h-1}\ge2011\;\Rightarrow\;h-1\ge11\,(2^{11}=2048)\;\Rightarrow\;h\ge12$$

选 C。

易错提醒

① 叶子数下界推高度：2^(h−1) ≥ 叶子数；② 对照总结点版本：2^h−1 ≥ n。