- 不同的二叉搜索树
image.png
思路:(https://www.jianshu.com/p/1186cf3a3ab4)
设f(n) = 节点个数为n组成的二叉搜索数种数
假定根节点为k,比k小的值都存在与k树的左子树,此处组成的左子树情况有 f(k-1)种,而比k大的值都存在与右子树,因此有f(n-k)种
由于左右子树的情况是相互独立的,因此根节点为k的二叉搜索树总共有f(n-k)*f(k-1)种
则f(n)的问题就等价于--k从1到n的所有组成二叉搜索树种类之和:f(n) = f（0）f（n-1）+f（1）f（n-2）+……+f（n-1）f（0）
最后，令f(0) = 1.f(1)=1
卡特兰数的递推式，答案不言而喻，即为f（n）=h（n）= C（2n,n）/（n+1）= c（2n,n）-c（2n,n-1）（n=0，1，2，……）。
int numTrees(int n) {
//卡特兰数,C(2n,n)/(n+1)
long long ans=1;
int i;
for(i=1;i<=n;++i)
ans=ans*(i+n)/i;
ans/=i;
return (int)ans;
}
网友评论