本文主要是介绍力扣96-不同的二叉搜索树（Java详细题解），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：96. 不同的二叉搜索树 - 力扣（LeetCode）
前情提要：
因为本人最近都来刷dp类的题目所以该题就默认用dp方法来做。
dp五部曲。
1.确定dp数组和i下标的含义。
2.确定递推公式。
3.dp初始化。
4.确定dp的遍历顺序。
5.如果没有ac打印dp数组 利于debug。
每一个dp题目如果都用这五步分析清楚，那么这道题就能解出来了。
题目思路:
该题要求n个节点所组成的二叉搜索树有多少种。
首先我们得知道什么是二叉树搜索树。
二叉树搜索树首先是一个二叉树，即每一个节点最多只有俩个子节点，且左孩子的值都比父节点小，右孩子的值都比父节点大。
这是二叉树搜索的特性，一定要利用起来。
然后我们在运用递归五部曲来进行分析。
1.确定dp数组和i下标的含义。
dp[i] 就是 由i个节点构成的不相同的二叉搜索树的种数。
以下分析如果想不清楚，就来回想一下dp[i]的定义
2.确定递推公式。
确定递推公式之前，我们先找规律。
当n为1的时候有一棵树，n为2有两棵树，这个是很直观的。
来看看n为3的时候，有哪几种情况。
显然由有三种情况
当1为头结点的时候，其右子树有两个节点，看这两个节点的布局，是不是和 n 为2的时候两棵树的布局是一样的啊！
（可能有同学问了，这布局不一样啊，节点数值都不一样。别忘了我们就是求不同树的数量，并不用把搜索树都列出来，所以不用关心其具体数值的差异）
当3为头结点的时候，其左子树有两个节点，看这两个节点的布局，是不是和n为2的时候两棵树的布局也是一样的啊！
当2为头结点的时候，其左右子树都只有一个节点，布局是不是和n为1的时候只有一棵树的布局也是一样的啊！
发现到这里，其实我们就找到了重叠子问题了，其实也就是发现可以通过dp[1] 和 dp[2] 来推导出来dp[3]的某种方式。
思考到这里，这道题目就有眉目了。
dp[3]，就是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量
元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量
元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量
元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量
有2个元素的搜索树数量就是dp[2]。
有1个元素的搜索树数量就是dp[1]。
有0个元素的搜索树数量就是dp[0]。
所以dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]。
由此可得当i为3时，dp[3]的递推关系。
所以dp[i] += dp[ j - 1] * dp[ i - j];
j是指当j为根节点的情况。i为3时需要根节点i为 1,2,3的这些情况，所以我们需要一个j来遍历我们根节点小与等于i的这些情况。
那dp[j - 1]是什么呢,其实就是当j 为根节点时，他的左子树的情况，当j为根节点 他的左子树节点肯定比j小。即有j - 1个节点所构成的二叉搜索树的个数。
dp[i - j]就是他的右子树的情况，他的右子树肯定比j大，因为是用j来遍历i，所以他的右子树的节点就是[i - j]了。
这样我们就得到了递推公式。
3.dp初始化。
我们应该初始化dp[0]还是dp[1]或者dp[2]呢？
我们应该初始化dp[0] = 1。
为啥为1不为0呢?
我们看看dp数组的含义。dp[i] 就是 由i个节点构成的不相同的二叉搜索树的种数。
0个节点其实也是二叉搜索树，即空节点也是一种二叉搜索树，所以我们dp[0] = 1。
其实dp[1]可以由dp[0]来推出。当只有一个节点时，他的根节点只有为1一种情况，他的左右节点都为dp[0]所以dp[1] = dp[0] * dp[0] = 1。
4.确定dp的遍历顺序。
由递推公式，我们可以看出dp[i] 是需要dp[i - j]的，即先要确定[i - j]，才能确定i。
所以我们的遍历顺序一定是要从前往后的。
5.如果没有ac打印dp数组 利于debug。
最后dp[i]模拟后情况就是这样，大家可以打印dp数组对着看看哪与你的不符。
分析完毕，我们来看看最终代码。
class Solution {public int numTrees(int n) {//递推要不断的找规律 最后确定递推公式//dp[i] 表示的就是i个节点所构成二叉搜索树的种树int [] dp = new int [n + 1];dp[0] = 1;for(int i = 1;i <= n;i ++){//这里面的j 其实就相等于当头节点为j的情况//等于它左子树的情况乘以右子树的情况for(int j = 1;j <= i ;j ++){dp[i] += dp[j - 1] * dp[i - j];}}return dp[n];}
}
怎么样，分析过程很复杂，而代码缺不超过20行，递推代码是不是很精简。
所以面对dp问题，我们要善于找规律，并按照动规五部曲走就好啦。
这一篇博客就到这了，如果你有什么疑问和想法可以打在评论区，或者私信我。
我很乐意为你解答。那么我们下篇再见！
这篇关于力扣96-不同的二叉搜索树（Java详细题解）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
