本文主要是介绍力扣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详细题解)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!