【一天一道LeetCode】#96. Unique Binary Search Trees
2024-10-12 21:41:50
一天一道LeetCode
本系列文章已全部上传至我的github,地址:ZeeCoder‘s Github
欢迎大家关注我的新浪微博,我的新浪微博
欢迎转载,转载请注明出处
(一)题目
Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?
For example,
Given n = 3, there are a total of 5 unique BST’s.
(二)解题
题目大意:给定一个数n,找出1~n组成的二叉搜索树的个数!
可以参考【一天一道LeetCode】#95. Unique Binary Search Trees II
如果单单求个数的话,可以简化。
n=1时,num=1;n=2时,num=2;n=3时,num=5!
可以找出规律,num[i] = num[left]*num[right]!i从1取到n,就为num[n]的值。left和right为左右的节点个数。(节点个数小于等于1的时候记二叉搜索树个数为1)
以题目中的例子为例,取1为根节点,2,3组成的二叉搜索树个数为2(right),左边为1,所以1为根节点的二叉搜索树个数为2,依次可以算出,2为根节点时个数为1,3为根节点的个数为2,加起来为5!
class Solution {
public:
int numTrees(int n) {
vector<int> num(n+1,-1);//存放i个节点存放的二叉搜索树个数
int ret = calNumTrees(1,n,num);
return ret;
}
int calNumTrees(int start , int end , vector<int>& num)
{
if(num[end - start +1] != -1) return num[end - start +1];
if(start >= end) return 1;//当少于等于1个节点时,二叉搜索树个数记为1
int temp = 0;
for(int i = start ; i <= end ; i++)//依次以1到n为根节点
{
int left = calNumTrees(start,i-1,num);//左边二叉搜索树的个数
int right = calNumTrees(i+1,end,num);//右边二叉搜索树的个数
temp +=(left*right);
}
if(num[end - start +1] == -1) num[end-start+1] = temp;//num[i]存放1~i组成的个数
return temp;
}
};
最新文章
- LSOF 安装与使用
- ruby日记1
- C#中DataTable排序、检索、合并等操作实例
- NodeJS优缺点及适用场景讨论
- 你所不知道的SQL Server数据库启动过程(用户数据库加载过程的疑难杂症)
- hdu 3183 贪心
- linux内核中的min(x, y)和max(x, y)宏定义
- 从 IT 的角度思考 BIM(一):面向对象
- 查看Linux发行版的名称和版本号
- JS常用验证方法
- java实现发送短信
- Openjudge-计算概论(A)-计算书费
- HTML5 进阶系列:canvas 动态图表
- hdu 5274 树链剖分
- maven压缩js css
- SAS 创建新变量
- 【转】Java基础——容器分类
- 安装Docker,Asp.net core
- .net源码调试 http://referencesource.microsoft.com/
- django使用表单