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

题目

一棵结点数为 $2015$ 的二叉树最多有_个叶子结点。

答案

1008

题解

考点定位

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

解题过程

n₀=n₂+1、n=n₀+n₁+n₂ ⇒ n₀ ≤ (n+1)/2（n₁=0 时最大，满树）：

$$(2015+1)/2=1008$$

答案：1008。

易错提醒

① n₁=0 ⇒ 满二叉树（结点数奇数 2015 ✓）；② n₀=n₂+1、n=2n₀+n₁−1 ⇒ n₀=(n−n₁+1)/2。