C# leetcode 之 096 不同的二叉搜索树
2024-10-06 12:06:24
C# leetcode 之 096 不同的二叉搜索树
题目描述
给定一个整数 n,求以 1 ... n 为节点组成的二叉搜索树有多少种?
二叉搜索树定义
左子树上所有节点的值小于根节点, 右子树上左右节点的值大于根节点, 并且左右子树也为二叉搜索树
解题思路
根据二叉搜索树定义可知, 针对 1 .. n 的排序序列, 选取其中任意一个元素i则1到i-1的元素为左子树节点, i+1到n为右子树的节点. 题目中问的是一共有多少种二叉树, 所以其实不用关心二叉树中节点的值. 由此可知一个树只要节点数相同则生成的二叉搜索树的数量相同. 我们在求解的过程中可以将不同的节点数对应的二叉搜索树的数量存到一个字典中. 又因为前面提到的选取i后可以将问题划分为更小的问题. 所以符合动态规划的特性. 下面尝试使用动态规划进行分析.
我们假设 1 .. n 中包含的二叉树个数为 G(n) 则可得出公式
\[G(n) = \sum_{i=1}^{n} G(i - 1) * G(n - i)
\]
\]
其中 i - 1
为左子树的元素个数, n - i
为右子树的元素个数, 并且G(0)为0
代码实现
实现方式1: 迭代实现
public int NumTrees(int n)
{
var ar = new int[n + 1];
ar[0] = 1;
for (var i = 1; i <= n; i++)
{
var count = 0;
for (var j = 1; j <= i; j++)
{
count += dic[j - 1] * dic[i - j];
}
dic[i] = count;
}
return dic[n];
}
实现方式2: 递归实现
private readonly IDictionary<int, int> _dic = new Dictionary<int, int>
{
[0] = 1
};
public int NumTrees(int n)
{
if (_dic.TryGetValue(n, out var val))
{
return val;
}
var count = 0;
for (var i = 1; i <= n; i++)
{
count += NumTrees(i - 1) * NumTrees(n - i);
}
_dic[n] = count;
return count;
}
最新文章
- UML类图与面向对象设计原则
- 数据库日常维护-CheckList_02有关数据库备份检查
- jQuery HTML 操作
- nodejs events模块
- auto refresh iframe
- 【BZOJ】2157: 旅游
- paip.抓取网页内容--java php python
- MySQL和OneSQL并行插入性能对比
- puppet证书重申
- [转载] Cassandra入门 框架模型 总结
- 线程池与Python中的GIL
- 使用nodeJS的 crypto模块来为你的密码hash加盐
- FORM内置系统变量
- BeyondCompare使用一段时间后会因“许可证密钥已被撤销:3281-0350“而无法使用
- Mysql取随机数据效率测试(200W条中读取100条)
- 【详解】ThreadPoolExecutor源码阅读(三)
- oracle ebs常规小看点
- github注册与使用
- devise在引擎中安装后,设置访问自定义页面
- linux下搭建禅道项目管理系统
热门文章
- 深度汉化GCompris-qt,免费的幼儿识字软件
- EL十一大内置对象
- [ProblemSolving][Ubuntu][LyX] The selected document class ... requires external files that are not available...
- Hyper-V安装CentOS 8问题
- 关于SpringBoot 1.x和2.x版本差别
- inkscape 无法打开文档属性
- 线程、进程概念与Android系统组件的关系
- ActiveMQ学习总结------原生实战操作(下)03
- idea 新建项目 coding上新建项目 idea推送到coding
- 04-12 scikit-learn库之随机森林