给定一个整数n,有一棵n个节点的二叉搜索树,节点值依次为1,2,…,n。求这棵二叉搜索树有多少种可能的形状。 由于输出结果较大,故要求结果对1e9+7取模后输出 不失一般性,如果n=0,可能的形状为1 在不使用STL容器的情况下用C++实现
时间: 2024-03-03 21:53:08 浏览: 17
题目描述
给定一个整数n,有一棵n个节点的二叉搜索树,节点值依次为1,2,…,n。求这棵二叉搜索树有多少种可能的形状。
由于输出结果较大,故要求结果对1e9+7取模后输出
不失一般性,如果n=0,可能的形状为1
算法思路
此题为卡特兰数的经典应用,卡特兰数的递推公式为:
C[0] = C[1] = 1;
for (int i = 2; i <= n; i ++ )
for (int j = 0; j < i; j ++ )
C[i] += C[j] * C[i - j - 1];
其中C[i]表示二叉搜索树有i个节点时的形状数。
时间复杂度
时间复杂度为 $O(n^2)$
空间复杂度
空间复杂度为 $O(n)$
C++代码
```cpp
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
const int mod = 1e9 + 7;
int n;
int f[N];
int main()
{
cin >> n;
f[0] = f[1] = 1;
for (int i = 2; i <= n; i ++ )
for (int j = 0; j < i; j ++ )
f[i] = (f[i] + (long long)f[j] * f[i - j - 1]) % mod;
cout << f[n] << endl;
return 0;
}
```