LeetCode笔记:96. Unique Binary Search Trees
2023-03-15 23:22:38 时间
问题:
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.
image.png
大意:
给出n,包含1~n这些节点可以形成多少个不同的BST(二叉查找树)? 比如, 给出n = 3,有5个不同的BST:
image.png
思路:
二叉查找树的性质是左子节点一定小于父节点,右子节点一定大于父节点。
我们思考一下可以发现,要形成不同的二叉树,最基本的分类是1n各自都做一次根节点。在它们作为根节点时,又分别还有多少种不同的组合方式呢?由于这是一个二叉查找树,那么根节点的左边一定都是小于他的数,右边一定都是大于它的数,所以1n就会被分成两部分去放置,这时候由可以分别把左子节点、右子节点分别看成要安放一部分数字的根节点,又变成了一样的规律。
所以假设以i为根节点,可能的组合情况为F(i,n),而G(n)为输入n后的结果。则
F(i,n) = G(i-1)*G(n-i)
也就是左子节点以下的可能数量乘以右子节点以下的可能数量。
而因为1~n都可能作为根节点,所以最终的值是它们的和,也就是
G(n) = F(1,n) + F(2,n) + …… +F(n,n)
换算一下就是
G(n) = G(0) * G(n-1) + G(1) * G(n-2) + …… + G(n-1) *G(0)
其中我们可以直接看出 G(0) = G(1) = 1。这个作为初始值来递归计算就可以了,要知道G(n),我们必须把前面的数都计算出来。
代码(Java):
public class Solution {
public int numTrees(int n) {
int[] res = new int[n+1];
res[0] = 1;
res[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i; j++) {
res[i] += res[j-1] * res[i-j];
}
}
return res[n];
}
}
相关文章
- 金融服务领域的大数据:即时分析
- 影响大数据、机器学习和人工智能未来发展的8个因素
- 从0开始构建一个属于你自己的PHP框架
- 如何将Hadoop集成到工作流程中?这6个优秀实践必看
- SEO公司使用大数据优化其模型的5种方法
- 关于Web Workers你需要了解的七件事
- 深入理解HTTPS原理、过程与实践
- 增强分析:数据和分析的未来
- PHP协程实现过程详解
- AI专家:大数据知识图谱——实战经验总结
- 关于PHP的错误机制总结
- 利用数据分析量化协同过滤算法的两大常见难题
- 怎么做大数据工作流调度系统?大厂架构师一语点破!
- 2019大数据处理必备的十大工具,从Linux到架构师必修
- OpenCV中的KMeans算法介绍与应用
- 教大家如果搭建一套phpstorm+wamp+xdebug调试PHP的环境
- CentOS下三种PHP拓展安装方法
- Go语言HTTP Server源码分析
- Go语言HTTP Server源码分析
- 2017年4月编程语言排行榜:Hack首次进入前五十