NOIP 普及 2016 第一轮 第 22 题：2016 个结点的二叉树最少叶子数

题目

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

答案

1

题解

考点定位

本题考「二叉树叶子数最少」,对应大纲 3.2.2 二叉树（难度【2】）。

解题过程

2016 结点二叉树最少叶子：让每层只有一个二结点（链式挂单孩子）：n₀=n₂+1、n₁=2016−n₀−n₂=2015−2n₂。取 n₁ 最大：n₂=0 ⇒ n₀=1？n₂=0 时全是一度结点——n₀=1（一条链只有一个叶子）✓。

答案：1。

易错提醒

① 最少叶子 = 1（链状树）；② n₀=n₂+1 中 n₂=0 ⇒ n₀=1、n₁=2015。