☆打卡算法☆LeetCode 96、不同的二叉搜索树 算法解析
☆打卡算法☆LeetCode 96、不同的二叉搜索树 算法解析
恬静的小魔龙
发布于 2022-08-07 10:22:20
发布于 2022-08-07 10:22:20
一、题目
1、算法题目
“给定一个整数n，求由n个节点组成的节点值从1到n的互不相同的搜索二叉树。”
题目链接：
来源：力扣（LeetCode）
链接：96. 不同的二叉搜索树 - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
image.png
示例 1：
输入： n = 3
输出： 5示例 2：
输入： n = 1
输出： 1二、解题
1、思路分析
这道题95题【不同的二叉搜索树 Ⅱ】很相似，不同的点在于这道题要找出互不相同的二叉搜索树。
上一题我们使用了递归的方法，找出所有能构建的二叉搜索树，然后再在其中找出合法的二叉搜索树。
而在遍历每个数字的过程中，可以将该数字作为树根，然后将1...i-1作为左子树，i+1...n作为右子树，然后按照同样的方式递归构建左子树和右子树。
也就是把一个问题分成两个小问题，因此可以使用动态规划来解这道题：
- 假设n个节点存在二叉排序树的个数为Gn，然后每个数字作为根也就是f(1)-f(n)，则
- G(n)=f(1)+f(2)+f(3)+f(4)+...+f(n)
- 当i为根节点时，其左子树节点数为1...i-1，右子树的节点数为i+1...n，则
- f(i)=G(i-1) * G(n-i)
- 综合两个公式可以得到卡特兰数公式：
- G(n) = G(0) * G(n-1) + G(1) * (n-2) + ... + G(n-1) * G(0)
2、代码实现
代码参考：
class Solution {
public int numTrees(int n) {
// 提示：我们在这里需要用 long 类型防止计算过程中的溢出
long C = 1;
for (int i = 0; i < n; ++i) {
C = C * 2 * (2 * i + 1) / (i + 2);
}
return (int) C;
}
}
image.png
3、时间复杂度
时间复杂度 ： O(n)
其中n表示二叉搜索树的节点个数。
空间复杂度： O(1)
只需要常量级的空间存放变量。
三、总结
这里分享一个面向测试用例的编程代码，非常的秀：
class Solution {
public:
int numTrees(int n) {
switch(n){
case 1: return 1;
case 2: return 2;
case 3: return 5;
case 4: return 14;
case 5: return 42;
case 6: return 132;
case 7: return 429;
case 8: return 1430;
case 9: return 4862;
case 10: return 16796;
case 11: return 58786;
case 12: return 208012;
case 13: return 742900;
case 14: return 2674440;
case 15: return 9694845;
case 16: return 35357670;
case 17: return 129644790;
case 18: return 477638700;
case 19: return 1767263190;
default: return 0;
}
}
};因为答案的值是固定的，所以这么写。。。好像也能通过。。。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-02-08，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录