第九章动态规划——不同的搜索二叉树

力扣题号：96. 不同的二叉搜索树 - 力扣（LeetCode）

题目描述

示例 1：

示例 2：

提示：

思路

什么是二叉搜索树

发现规律

当n为1和n为2时

当输入的n为3时

如果是以 1 为头节点

如果是以2为头节点

如果是以3为头节点

发现

动态规划五部曲

（1）dp数组的下标及其含义

（2）确定递推公式

（3）初始化递推数组

（4）确定遍历顺序

（5）根据题意推出dp数组对照

动态规划代码实现

代码实现（卡塔兰数）

卡塔兰数

卡塔兰数代码实现

总结

力扣题号：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节点

$n_{head=1}=left_{0} \times right_{2}$

那如果头节点为2的时候，情况就是，左子树1节点×右子树1节点

$n_{head=2}=left_{1} \times right_{1}$

那如果头节点为3的时候，情况就是，左子树2节点×右子树0节点

$n_{head=3}=left_{2} \times right_{0}$

根据上面的推导，那么我们这里的dp[3]与dp[2],dp[1],dp[0]的关系就如下公式：

$dp[3]=d[0]\times dp[2]+dp[1] \times dp[1]+dp[2] \times dp[0]$

amazing~~~ 酱紫就可以动态规划了

动态规划五部曲

（1）dp数组的下标及其含义

这里我们是要求解当节点数是n的时候的，不同的二叉搜索树的数量，因此我们这里的

$dp[i]$ ,就是n=i时候的二叉搜索树的种类数量。

（2）确定递推公式

我们再来思考一下，这是一个搜索二叉树对吧，我们的dp[i]是由以1为头结点的情况，以2为头结点的情况，以3为头结点的情况一起求出来的。

如果我的头结点现在是 j ，那么左子树就有 j - 1个节点，因为这是二叉搜索树，那么右子树就有 i - j 个节点。

那么根据刚才的结论我们也可以得出这样的递推公式如下（当有i个节点，头结点是j的时候）：

$dp[i] += dp[j-1] \times dp[i-j]$

（3）初始化递推数组

根据上面的推导，我们的递推数组推到n为3的时候就可以了，如下所示：

$dp[0]=1$

$dp[1]=1$

$dp[2]=2$

$dp[3]=5$

（4）确定遍历顺序

那肯定是从小了往大遍历了。这还说啥了

（5）根据题意推出dp数组对照

当n=10的时候如下所示：

[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796]

动态规划代码实现

java">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）得名。

卡塔兰数序列的公式为：

$C_{0}=1,C_{n+1}=\frac{2(2n+1)}{n+2}C_{n}$

它出现在各种计数问题中，例如：

计算有效的括号匹配序列数量
计算在笛卡尔平面上从(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的数量。之后把它们相乘即可。

所以，根据它的公式我们可以直接得出答案了。

卡塔兰数代码实现

java">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

java">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。