class Solution {
public:
int numTrees(int n) {
}
};
96. 不同的二叉搜索树
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例 1：
输入：n = 3 输出：5
示例 2：
输入：n = 1 输出：1
提示：
1 <= n <= 19
相似题目
原站题解
96. 不同的二叉搜索树
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例 1：
输入：n = 3 输出：5
示例 2：
输入：n = 1 输出：1
提示：
1 <= n <= 19相似题目
原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 2 MB, 提交时间: 2024-04-22 09:36:01
func numTrees(n int) int {
C := 1
for i := 0; i < n; i++ {
C = C * 2 * (2 * i + 1) / (i + 2);
}
return C
}
func numTrees2(n int) int {
G := make([]int, n + 1)
G[0], G[1] = 1, 1
for i := 2; i <= n; i++ {
for j := 1; j <= i; j++ {
G[i] += G[j-1] * G[i-j]
}
}
return G[n]
}
javascript 解法, 执行用时: 58 ms, 内存消耗: 49 MB, 提交时间: 2024-04-22 09:35:37
/**
* @param {number} n
* @return {number}
*/
var numTrees = function(n) {
const G = new Array(n + 1).fill(0);
G[0] = 1;
G[1] = 1;
for (let i = 2; i <= n; ++i) {
for (let j = 1; j <= i; ++j) {
G[i] += G[j - 1] * G[i - j];
}
}
return G[n];
};
// 数学公式
var numTrees2 = function(n) {
let C = 1;
for (let i = 0; i < n; ++i) {
C = C * 2 * (2 * i + 1) / (i + 2);
}
return C;
};
python3 解法, 执行用时: 35 ms, 内存消耗: 16.4 MB, 提交时间: 2024-04-22 09:35:00
class Solution:
def numTrees(self, n: int) -> int:
C = 1
for i in range(0, n):
C = C * 2*(2*i+1)/(i+2)
return int(C)
def numTrees2(self, n: int) -> int:
G = [0]*(n+1)
G[0], G[1] = 1, 1
for i in range(2, n+1):
for j in range(1, i+1):
G[i] += G[j-1] * G[i-j]
return G[n]
java 解法, 执行用时: 0 ms, 内存消耗: 39.4 MB, 提交时间: 2024-04-22 09:34:00
class Solution {
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];
}
// 数学
public int numTrees2(int n) {
// 提示：我们在这里需要用 long 类型防止计算过程中的溢出
long C = 1;
for (int i = 0; i < n; ++i) {
C = C * 2 * (2 * i + 1) / (i + 2);
}
return (int) C;
}
}
cpp 解法, 执行用时: 3 ms, 内存消耗: 6.9 MB, 提交时间: 2024-04-22 09:33:09
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;
}
// 动态规划
int numTrees2(int n) {
vector<int> G(n + 1, 0);
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];
}
};
golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2021-08-03 09:49:25
func numTrees(n int) int {
return catalanNumber(n, map[int]int{})
}
func catalanNumber(n int, buffer map[int]int) int {
if n < 2 {
return 1
}
if c, ok := buffer[n]; ok {
return c
}
ans := 0
n--
for i := 0; i <= n; i++ {
ans += catalanNumber(i, buffer) * catalanNumber(n - i, buffer)
}
buffer[n+1] = ans
return ans
}