题目出处
题目描述
个人解法
思路：
todo
代码示例：（Java）
todo
复杂度分析
todo
官方解法
方法1：动态规划
思路：
代码示例：（Java）
public class Solution1 {
public int numTrees(int n) {
int[] G = new int[n + 1];
G[0] = 1;
G[1] = 1;
for (int i = 2; i <= n; ++i) {
for (int j = 1; j <= i; ++j) {
G[i] += G[j - 1] * G[i - j];
}
}
return G[n];
}
}
复杂度分析
方法2:数学
思路：
代码示例：（Java）
public class Solution2 {
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)。我们只需要常数空间存放若干变量。
考察知识点
收获
1.卡特兰数
