96. 不同的二叉搜索树
题目描述
输入整数 n。用值为 1 到 n 的 n 个节点，每个值恰好用一次，搭成二叉搜索树。
二叉搜索树中，每个节点左子树的值都比它小，右子树的值都比它大。
返回结构互不相同的这种树共有多少棵。
示例 1
输入：n = 3 输出：5
解释：以 1、2、3 为根分别有 2、1、2 种，共 5 种。
示例 2
输入：n = 1 输出：1
数据范围
1 <= n <= 19
解题思路：动态规划
设 g[i] 为 i 个节点能组成的 BST 种数，它只取决于节点个数，与具体的值无关。在 1..i 中选 j 作根，左子树由 j-1 个更小的值组成，右子树由 i-j 个更大的值组成，两边独立，所以有 g[j-1]·g[i-j] 种。对所有 j 求和就是 g[i]，即卡特兰数。
为什么正确
计算 g[i] 时，g[0..i-1] 都已经是最终值。
复杂度分析
时间 O(n²)，空间 O(n)。
易错点
g[0] 必须是 1 而不是 0，否则左右子树有一边为空的情况会被乘成 0；左右子树的数量要相乘，不是相加。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def numTrees(self, n):
g = [0] * (n + 1)
g[0] = 1
for i in range(1, n + 1):
for j in range(1, i + 1):
g[i] += g[j - 1] * g[i - j]
return g[n]class Solution {
public int numTrees(int n) {
long[] g = new long[n + 1];
g[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
g[i] += g[j - 1] * g[i - j];
}
}
return (int) g[n];
}
}class Solution {
public:
int numTrees(int n) {
vector<long long> g(n + 1, 0);
g[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
g[i] += g[j - 1] * g[i - j];
}
}
return (int)g[n];
}
};func numTrees(n int) int {
g := make([]int, n+1)
g[0] = 1
for i := 1; i <= n; i++ {
for j := 1; j <= i; j++ {
g[i] += g[j-1] * g[i-j]
}
}
return g[n]
}var numTrees = function(n) {
const g = new Array(n + 1).fill(0);
g[0] = 1;
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= i; j++) {
g[i] += g[j - 1] * g[i - j];
}
}
return g[n];
};function numTrees(n: number): number {
const g: number[] = new Array(n + 1).fill(0);
g[0] = 1;
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= i; j++) {
g[i] += g[j - 1] * g[i - j];
}
}
return g[n];
}其他解法
动态规划从“枚举根节点”推出递推，是自己能想到的做法；认出它是卡特兰数后，可以用 O(n) 公式直接计算。
解法 2：卡特兰数公式 时间 O(n)，空间 O(1)
主解法的递推 G(n) = Σ G(j-1)·G(n-j) 正是卡特兰数的定义，而卡特兰数有更简单的递推式：C(0) = 1，C(i+1) = C(i) · 2(2i+1) / (i+2)。从 C(0) 开始连乘 n 次即可得到答案，每一步先乘后除结果仍是整数。
时间从 O(n²) 降到 O(n)，空间 O(1)。需要知道卡特兰数的结论，而且中间的乘积会比答案大，C++/Java 要用 64 位整数。
class Solution:
def numTrees(self, n):
c = 1
for i in range(n):
# C(i+1) = C(i) * 2(2i+1) / (i+2)
c = c * 2 * (2 * i + 1) // (i + 2)
return cclass Solution {
public int numTrees(int n) {
long c = 1;
for (int i = 0; i < n; i++) c = c * 2 * (2 * i + 1) / (i + 2);
return (int) c;
}
}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;
}
};func numTrees(n int) int {
c := 1
for i := 0; i < n; i++ {
c = c * 2 * (2*i + 1) / (i + 2)
}
return c
}var numTrees = function(n) {
let c = 1;
for (let i = 0; i < n; i++) c = c * 2 * (2 * i + 1) / (i + 2);
return Math.round(c);
};function numTrees(n: number): number {
let c = 1;
for (let i = 0; i < n; i++) c = c * 2 * (2 * i + 1) / (i + 2);
return Math.round(c);
}