不同的二叉搜索树
程序员文章站
2022-07-16 11:53:13
...
好吧我是懒狗,看到这个题,第一反应就是,递归去做,这个题也没给时间限制,我就试了一下递归。
int numTrees(int n)
{
int sum = 0;
if(n == 1 || n == 0)
{
return 1;
}
for(int i = 1;i <= n;++i)
{
sum +=numTrees(i-1) * numTrees(n - i);
}
return sum;
}
大概就是这样一个题,最早的一个想法就是每次选择不同的结点作为根节点,左树*右树递归的做法,当然是完全ok的,时间复杂度太高,解决方案呢就是用数组去保存计算过的值,重新进行计算。这是一种方法我没写。我是懒狗。
按照上面的思路进行逆推,就跟斐波那契数列一样,递归从尾部到头部,又可以从头部到尾部。
int numTrees(int n)
{
vector<int> G(n+1,0);
G[0] = 1;
G[1] = 1;
for (int i = 2; i <= n; ++i)
{
for (int j = 1; j <= i; ++j)
{
G[i] += G[j - 1] * G[i - j];
}
}
return G[n];
}
我说这个和斐波那契数列差不多一样,该不会有人反驳我吧,不会吧不会吧。