令\(f_n\)表示\(n\)个点的二叉树个数；\(g_n\)表示\(n\)个点的所有\(f_n\)棵二叉树的叶节点总数。
我们发现一个规律：\(g_n=nf_{n-1}\)
证明：
对于每棵\(n\)个点的二叉树，如果里面有\(k\)个叶节点，那么我们分别把这\(k\)个叶子删去会得到\(k\)棵\(n-1\)个点的二叉树，那么一颗\(k\)个叶子节点的树对应\(k\)棵\(n-1\)的树
而每一颗\(n-1\)的树有\(n\)个地方可以挂叶子。
\(f_n=\sum_{i=1}^{n-1}f_if_{n-1-i}\)
\(f_1=1\)
可以发现\(f_n\)是卡特兰数
带入公式可以得到\(Ans=\frac{n(n+1)}{2(2n?1)}\)
原文：https://www.cnblogs.com/zzy2005/p/11835866.html