96.不同的二叉搜索树——medium

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

示例:
**
输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-binary-search-trees

思路：
假设 n 个节点存在二叉排序树的个数是 G (n)，令 f(i) 为以 i 为根的二叉搜索树的个数，则
G(n) = f(1) + f(2) + f(3) + f(4) + ... + f(n)
对于f(i)来说:
i
/ \
1~i-1 i+1 ~ n
由图可得出：f(i) = G(i-1)*G(n-i)
由以上两式可得出：
G(n) = G(0)*G(n-1) + G(1)*G(n-2) + …… +G(n-1)*G(0)
时间复杂度为O(n),空间复杂度为O(n)。
查阅资料可知我们推出来的公式叫：卡特兰数
有以下几个递推关系：

1. h(n)=h(n-1)(4n-2)/(n+1)
2. 递推关系的解为：h(n)=C(2n,n)/(n+1) (n=0,1,2,…)
3. 递推关系的另类解为：h(n)=C(2n,n) - C(2n,n-1) (n=0,1,2,…)

使用关系1进行递推即可。
复杂度分析：
时间复杂度为O(n)
空间复杂度为O(1)

var numTrees = function (n) {
    let C = 1;
    for (let i = 0; i < n; i++) {
        C *= 2 * (2 * i + 1) / (i + 2);
    }
    return C;
};