40.Unique Binary Search Trees(不同的二叉搜索树)
2024-10-07 16:31:17
Level:
Medium
题目描述:
Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?
Example:
Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST's:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
思路分析:
动态规划的思想,二叉树有个性质,就是左子树的节点值都比根小,右子树的节点值都比根大,题目说明二叉树的节点值是从1到n,所以我们能够确定如果根为k,那么左子树的值是1到k-1,右子树的值是k+1到n。还有一点是,对于一个根来说,唯一二叉树的数量是其左子树的数量乘上右子树的数量,这是简单的乘法原理。并且左右子树的形态数量跟具体的数没有关系,只跟这个树里有多少个节点有关。而根可以选择从1到n的任意数,唯一二叉树的总数,就是根为1到n的树相加。所以该问题化简为以k为根,其唯一左子树和右子树各有多少,这就是动态规划问题了,我们建立一个数组dp[ i ],代表节点数为i的唯一子树有多少个。显然dp[0]=dp[1]=1。
代码:
public class Solution{
public int numTrees(int n){
int []dp=new int[n+1]; //dp[i]代表的是节点数为i的唯一子树有多少个
dp[0]=dp[1]=1;
for(int i=2;i<=n;i++){//表示一共有多少的节点
for(int j=0;j<i;j++){ //表示左子树有多少节点
dp[i]=dp[i]+dp[j]*dp[i-j-1];
}
}
return dp[n];
}
}
最新文章
- Winform 中DataGridView控件添加行标题
- mongodb简介与增删该查
- eclipse 编译android程序 编译错误
- CF 706B 简单二分,水
- css样式reset
- windows下bat批处理实现守护进程
- My集合框架第六弹 左式堆
- Matlab实现二进制矩阵转换为十进制
- selenium webdriver 环境搭建--java
- jenkins tags
- Hadoop技巧(04):简易处理solr date 时区问题
- 小谈iOS屏幕适配问题
- AspNetCoreApi 跨域处理
- XV Open Cup named after E.V. Pankratiev. GP of America
- 吴裕雄 python 机器学习——Lasso回归
- Web API 2 自定义默认Identity Table Name
- luogu P4091 [HEOI2016/TJOI2016]求和
- Django MTV模式详解
- POJ2480 Longge&#39;s problem
- BZOJ NOIP提高组十连测第一场