3个结点可构成（）棵不同形态的二叉树。

[单选题]

3个结点可构成（）棵不同形态的二叉树。

查看正确选项

侯卿

假设这个问题的解为f（n），那么可以知道f（0）=f（1）=1。

现在先将一个点作为根节点，0个放左，n-1个放右，那么有f（0）f（n-1）种，再1个放左，n-2个放右，那么一共是f（1）f（n-2）种，以此类推直到n-1个放左，0个放右，将以上情况累加起来得到公式：

f(n) = f(n-1)f(0) + f(n-2)f(1) + ………. + f(1)f(n-2) + f(0)f(n-1)

这个序列想必大家都很熟悉了吧，嗯，就是卡特兰数，(和求n个点入栈问出栈可能数是一样的)。

这个递归函数的解就不推了，有兴趣可以自行google，解出来公式如下(有两种，记住任何一种都行)：

f(n) = C(2n,n)/(n+1) = (2n)! / ((n+1)!n!)

编辑于 2018-03-28 15:48:39 回复(0)

牛客670527190号

发表于 2021-05-28 12:49:19 回复(0)

A_C

卡特兰数（2n)!/((n+1)!n!)

发表于 2017-06-20 17:59:44 回复(1)

牛客233424611号

区分左子树与右子树

发表于 2021-11-30 20:17:15 回复(0)

提交观点

问题信息

树

上传者：阿奻_

难度：

4条回答 100收藏 3846浏览

扫一扫，把题目装进口袋