目录
力扣题号：96. 不同的二叉搜索树 - 力扣（LeetCode）
力扣题号：96. 不同的二叉搜索树 - 力扣（LeetCode）
注：下述题目描述和示例均来自力扣
题目描述
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例 1：
输入：n = 3 输出：5
示例 2：
输入：n = 1 输出：1
提示：
1 <= n <= 19
思路
如果我们通过观察就可以发现以下的规律。
在讲述这个规律之前，我们先说一下什么是二叉搜索树
什么是二叉搜索树
二叉搜索树（Binary Search Tree），也称为二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有以下性质的二叉树：
- 如果它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 如果它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
- 它的左、右子树也分别为二叉搜索树。
二叉搜索树的特性使得它在查找、插入、删除操作中表现出良好的效率，这些操作在平均和最好的情况下，时间复杂度可以达到 O(log n)。因此，二叉搜索树被广泛用作高效查找结构。
发现规律
我们假设我们的二叉搜索树的有三个节点，分别是 1，2，3， 当然了，这里只是为了清楚的解释这个问题，你这里的节点是1000,20000,30000000，都可以，只要是不一样大就行了。
我们这里设树节点的数量为n，
当n为1和n为2时
我们二叉搜索树的类型有如下图所示：
当输入的n为3时
如果是以 1 为头节点
那么右子树的分布肯定就和n为2时的分布就是一样的了。如下图所示：
如果是以2为头节点
那么左右子树的分布就都和n为1的情况相似了，如下图所示:
如果是以3为头节点
那么左子树的布局和n为2的情况仍然一致，如下图所示：
发现
其实n为3这个情况的每一种情况好像都可以由n为1和n为2，这两种情况都推出来。那么这层关系该如何的利用起来呢。
那如果头节点为1的时候，情况就是，左子树0节点×右子树2节点
那如果头节点为2的时候，情况就是，左子树1节点×右子树1节点
那如果头节点为3的时候，情况就是，左子树2节点×右子树0节点
根据上面的推导，那么我们这里的dp[3]与dp[2],dp[1],dp[0]的关系就如下公式：
amazing~~~ 酱紫就可以动态规划了
动态规划五部曲
（1）dp数组的下标及其含义
这里我们是要求解当节点数是n的时候的，不同的二叉搜索树的数量，因此我们这里的
,就是n=i时候的二叉搜索树的种类数量。
（2）确定递推公式
我们再来思考一下，这是一个搜索二叉树对吧，我们的dp[i]是由以1为头结点的情况，以2为头结点的情况，以3为头结点的情况一起求出来的。
如果我的头结点现在是 j ，那么左子树就有 j - 1个节点，因为这是二叉搜索树，那么右子树就有 i - j 个节点。
那么根据刚才的结论我们也可以得出这样的递推公式如下（当有i个节点，头结点是j的时候）：
（3）初始化递推数组
根据上面的推导，我们的递推数组推到n为3的时候就可以了，如下所示：
（4）确定遍历顺序
那肯定是从小了往大遍历了。这还说啥了
（5）根据题意推出dp数组对照
当n=10的时候如下所示：
[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796]
动态规划代码实现
import java.util.Arrays;
public class text {
public static void main(String[] args) {
int res = numTrees(10);
System.out.println(res);
}
public static int numTrees(int n) {
// 如果是3以及一下的数，直接输出
if(n <= 3){
if(n == 1){
return 1;
}else if(n == 2){
return 2;
}else{
return 5;
}
}
// new 出dp数组
int[] dp = new int[n + 1];
// 初始化dp数组
// 这里一定要把dp[0]初始化为1，这是很重要的
dp[0]=1;
dp[1]=1;
dp[2]=2;
dp[3]=5;
for(int i = 4;i <= n;i++){
for(int j = 1;j <= i; j++){
dp[i] += dp[j-1]*dp[i-j];
}
}
// 打印一下dp数组的值，也可以不打印，这里只是为了方便理解。
System.out.println(Arrays.toString(dp));
return dp[n];
}
}
这样之后直接打败了全世界的人。
代码实现（卡塔兰数）
在看了力扣的题解之后发现这其实还是一个数学方法。然后我就查了一查资料。
卡塔兰数
卡塔兰数是一种数学序列，在组合数学中经常出现，并以比利时数学家欧仁·卡塔兰（Eugène Charles Catalan）得名。
卡塔兰数序列的公式为：
它出现在各种计数问题中，例如：
- 计算有效的括号匹配序列数量
- 计算在笛卡尔平面上从(0, 0)到(n, n)的路径数量，且路径不越过y=x线
- 计算具有n+1个叶子节点的满二叉树数量，等等。
例如，前几个卡塔兰数是：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …
实际上，我们这个问题是卡塔兰数的一个典型应用。对于含有n个节点的二叉搜索树（BST），种类的数量是第n个卡塔兰数。
该问题可以被视为一个计数问题：在每个节点数上，我们都要计算所有合法的二叉搜索树。对于某个给定的节点数n，我们可以将每个数i (0 <= i < n)都试一遍作为根节点，然后递归地计算作为左子树的i个节点和作为右子树的n-i-1个节点可以形成的所有合法BST的数量。之后把它们相乘即可。
所以，根据它的公式我们可以直接得出答案了。
卡塔兰数代码实现
class Solution {
public int numTrees(int n) {
int C = 1;
for(int i = 0; i < n; i++){
C = C*2*(2*i+1)/(i+2);
}
return C;
}
}好好好 ，你敢写成这样是吧，你完啦
直接被制裁，那就用long
class Solution {
public int numTrees(int n) {
long C = 1;
for(int i = 0; i < n; i++){
C = C*2*(2*i+1)/(i+2);
}
return (int)C;
}
}
这也没啥提升啊，废了，我最爱的数学方法
总结
看似我们在学习动态规划的题目，但是一不小心又学习了一个数学知识，真的是a。
