NOIP 提高 2015 第一轮 第 22 题：结点数为 5 的不同形态的二叉树一共有_种。（结点数为 2 的二叉树一共有 2

题目

结点数为 $5$ 的不同形态的二叉树一共有_种。（结点数为 $2$ 的二叉树一共有 $2$ 种：一种是根结点和左儿子，另一种是根结点和右儿子。）

答案

42

题解

考点定位

本题考「二叉树形态计数」,对应大纲 2.1.5 卡特兰数（难度【4】）。

解题过程

n 结点二叉树形态数 = 卡特兰数 Cₙ：

$$C_5=\frac{1}{6}\binom{10}{5}=42$$

递推：C₀=1, C₁=1, C₂=2, C₃=5, C₄=14, C₅=42。

答案：42。

易错提醒

① 卡特兰数递推 Cₙ=ΣCᵢCₙ₋₁₋ᵢ（根+左右子树分配）；② 1,1,2,5,14,42,132 必背。