96. 不同的二叉搜索树

96. 不同的二叉搜索树

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;
}