题目

先序序列为 a,b,c,d 的不同二叉树的个数是()。

错因

A

记得用卡特兰数公式 ，但算 时算成了 65 或别的数（70 才对），。或者凭印象写 13——卡特兰数列前几项是 1, 1, 2, 5, 14, 42 …，记成"4 个节点 → 13"是把第几项数错。

C

，可是有人多加了一种"空树"或"根为空"的退化情况算成 15。空树并不在 4 节点二叉树的计数范围内，n=4 严格指 4 个节点。

D

直接套用 ❌ 或 ❌ 都对不上 16。最常见是误用 "每个节点 2 种孩子选择" 凑成 ——这不是真实的二叉树形态计数公式。也有人记错卡特兰数为 （取整 17，再调成 16），属于公式张冠李戴。

总解析

核心结论：n 个不同关键字、先序序列固定时，能形成的不同二叉树形态数 = 卡特兰数 。

为什么是卡特兰数：先序序列固定 → 根永远是序列首字母 a；剩下 b,c,d 在二叉树里分到左右子树时，必须保持原有的相对顺序（先序的递归结构决定的）。这就是"括号匹配 / 出栈序列计数"那一类组合问题，结果就是卡特兰数。

卡特兰数公式：

代入 ：

也可用递推：，。

n
0	1
1	1
2	2
3	5
4	14
5	42

记忆窍门：卡特兰数列 1, 1, 2, 5, 14, 42, 132 …——4 个节点对应 14、5 个节点对应 42，是 408 反复考的两个数。

同型考点：n 个不同元素入栈的不同出栈序列数、n 对括号的合法匹配数、n+1 个叶子的二叉树数——都是 。

最终答案是 B（14）。