96. 不同的二叉搜索树 卡特兰数

96. 不同的二叉搜索树

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

个人废话：

这个是卡特兰数的一个典型案例，太久没用到过，就忘了，看到基本没想起来。

下面介绍一下卡特兰数：

其前几项为（从第0项开始）：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, …

卡特兰数的经典问题：

1. 进出栈序列：
   n 个元素进栈序列为：1，2，3，4，...，n，则有多少种出栈序列

2. 括号序列
   n 对括号，则有多少种 “括号匹配” 的括号序列

3. 二叉树
   n + 1 个叶子节点能够构成多少种形状不同的（国际）满二叉树

4. 电影购票
   电影票一张 50 coin，且售票厅没有 coin。m 个人各自持有 50 coin，n 个人各自持有 100 coin。
   则有多少种排队方式，可以让每个人都买到电影票。

解题模板：

卡特兰数的通项：

卡特兰数递推式：

所以这一题，递推一下，注意爆ll。

代码：

class Solution {
public:
    int numTrees(int n) {
        vector<int> f(n+1,0);
        f[0] = 1;
        for (int i = 1; i <= n; i++) f[i] = f[i - 1] *1ll* (4 * i - 2) / (i + 1);
        return f[n];
    }
};