1.题目

题目描述：给定二叉树的节点总数 n，输出二叉树形态总数，n<= 1000
输入：
3
输出：
5

2.思路

n个结点组成的二叉树形态总数=卡特兰数=$C_m^n/(n+1)$，其中m=2n。
可以写一个Cmn函数将分子一块计算出来，最后除以n+1即可。
由于n=1000时，计算C会比较大，所以不能使用int型，而要使用long long型。

可以回顾一下【LeetCode96】不同的二叉搜索树（dp）虽然也是求卡特兰数，但那题则是给出以1、2、…、n为结点组成的二叉搜索树种数，即结点的大小是确定的，而本题的结点大小是不确定的，也不是组成二叉搜索树。

3.代码

#include <iostream>
using namespace std;

long long Cmn(long long n) {
	long long fengzi = 1, fengmu = 1;
	for (int i=2*n; i>n; i--) {
		fengzi *= i;
	}
	for (int i=n; i>=1; i--) {
		fengmu *= i;
	}
	return fengzi / fengmu;
}

int main() {
	long long N;
	cin >> N;
	cout << Cmn(N)/(N+1) << endl;
	//return 0;
	system("pause");
}


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
 

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/113842981