leetcode算法练习——不同的二叉搜索树

题目：

给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

示例：

代码如下：

长度为n的序列的不同二叉搜索树个数C(n)为卡塔兰数。

首先，设长度为$n$n,数$i$i作为根时，二叉搜索树的个数为$F(i,n)$F(i,n)
则$C(n)$C(n)=$\sum^n_{i=1}F(i,n)$∑i=1n​F(i,n)

当数$i$i作为根时，$1$1到$i-1$i−1和$i+1$i+1到$n$n分别构成$i$i的左子树和右子树。
且$1$1到$i-1$i−1构成的左子树数量可以用$C(i-1)$C(i−1)表示，$i+1$i+1到$n$n构成的右子树数量可以用$C(n-i)$C(n−i)表示。

因为长度为n的序列构成的二叉搜索树的数量只与序列长度有关，与序列里数的大小无关。
则$F(i,n)$F(i,n)=$C(i-1)*C(n-i)$C(i−1)∗C(n−i)

所以$C(n)$C(n)可以写成$C(n)$C(n)=$\sum^n_{i=1}C(i-1)*C(n-i)$∑i=1n​C(i−1)∗C(n−i)
这是卡塔兰数的形式。

卡塔兰数还可以写成这种形式：
$C(n)=C(n-1)*(4n-2)/(n+1)$C(n)=C(n−1)∗(4n−2)/(n+1)

特殊情况：$C(0)=1$C(0)=1，$C(1)=1$C(1)=1

class Solution {
public:
    int numTrees(int n) 
    {
        if (n==0) return 1;
        long C = 1;
        for(int i=1;i<=n;i++)
        {
            C = C*(4*i-2)/(i+1);
        }
        return C;
    }
};

运行结果：