“给定一个整数n,求由n个节点组成的节点值从1到n的互不相同的搜索二叉树。”
题目链接:
来源:力扣(LeetCode)
链接:96. 不同的二叉搜索树 - 力扣(LeetCode) (leetcode-cn.com)
给你一个整数 n
,求恰由 n
个节点组成且节点值从 1
到 n
互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。
示例 1:
输入: n = 3
输出: 5
示例 2:
输入: n = 1
输出: 1
这道题95题【不同的二叉搜索树 Ⅱ】很相似,不同的点在于这道题要找出互不相同的二叉搜索树。
上一题我们使用了递归的方法,找出所有能构建的二叉搜索树,然后再在其中找出合法的二叉搜索树。
而在遍历每个数字的过程中,可以将该数字作为树根,然后将1...i-1作为左子树,i+1...n作为右子树,然后按照同样的方式递归构建左子树和右子树。
也就是把一个问题分成两个小问题,因此可以使用动态规划来解这道题:
代码参考:
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;
}
}
时间复杂度 : 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;
}
}
};
因为答案的值是固定的,所以这么写。。。好像也能通过。。。