不同的二叉搜索树
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给你一个整数 n，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例 1
示例 2
模拟答题者思考
1. 暴力想法：像 #95 那样递归生成每一棵 BST 再数个数——思路正确，但只需求个数、不必建树，枚举再计数会多做大量重复子问题。
2. 重复在哪里？「区间 [1..k] 上有多少种 BST」只与 k 有关，与具体节点标签无关；选根 j 后，左、右子树的规模分别是 j-1 与 i-j，与父问题同形。
3. 关键转化：设 G(i) 为 i 个连续值能形成的 BST 种数。枚举根 j，左子树有 G(j-1) 种、右子树有 G(i-j) 种，互独立相乘：G(i) = Σj=1..i G(j-1)·G(i-j)，G(0)=1。这就是卡特兰数的递推。
4. 手推 n=3：G(0)=1；G(1)=1；G(2)=G(0)G(1)+G(1)G(0)=2；G(3)=G(0)G(2)+G(1)G(1)+G(2)G(0)=2+1+2=5，与示例一致。
5. 与 #95 的关系：#95 要对左右子树列表做笛卡尔积构造树；本题只需把同一分解下的方案数相乘再求和，是 #95 子问题的计数版 DP。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
dp[i] | int | 定义：用连续节点值 1..i（共 i 个节点）能构成的不同 BST 的结构种数维护： dp[0]=1 表示空树一种「占位」；对规模 i，枚举根 j∈[1,i]，左子树规模 j-1、右子树规模 i-j，BST 性质保证左右子树值域不交叉更新： dp[i] += dp[j-1] * dp[i-j]；答案为 dp[n] |
j | int | 定义：当前规模 i 下，作为 BST 根节点的值（也是第 j 个最小值）维护：根固定后，左子树只能从更小的 j-1 个值生成、右子树从更大的 i-j 个值生成，与子问题 dp[·] 同构更新： for j in range(1, i+1) 累加左右方案数的乘积 |
i | int | 定义：外层 DP 的规模，从 1 推到 n维护：计算 dp[i] 时，所有 dp[0]..dp[i-1] 必须已就绪更新： for i in range(1, n+1) |
落码步骤
1. 若 n==0（部分接口），可返回 0；本题 n≥1
2. 创建长度 n+1 的 dp，令 dp[0]=1
3. 对 i 从 1 到 n，令 dp[i]=0
4. 对 j 从 1 到 i：dp[i] += dp[j-1] * dp[i-j]
5. 返回 dp[n]
代码实现
class Solution:
def numTrees(self, n: int) -> int:
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
for j in range(1, i + 1):
dp[i] += dp[j - 1] * dp[i - j]
return dp[n]class Solution {
public:
int numTrees(int n) {
vector<long long> dp(n + 1, 0);
dp[0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= i; ++j) {
dp[i] += dp[j - 1] * dp[i - j];
}
}
return (int)dp[n];
}
};
// 时间 O(n²)，空间 O(n)；n≤19 时卡特兰数在 int 范围内复杂度分析
O(n²)（外层 i=1..n，内层枚举根 j）
O(n)（一维 dp 数组；卡特兰数递推）
常见坑
忘记 dp[0]=1：空子树在乘法里要当作「一种方案」，否则 j=1 或 j=i 的「只有一侧非空」会算成 0。
与 #95 混淆：本题只计数，不要 TreeNode 与笛卡尔积；转移公式相同，实现差一个「乘积 vs 拼树」。
内层循环上界：根 j 必须取遍 1..i，漏掉任一根都会少计；左右规模是 j-1 与 i-j，不要写成 j 与 i-j-1。
必测边界 Case
n = 1 → 1
n = 2 → 2（根 1 或根 2 各一种结构）
n = 3 → 5（与示例 1、#95 输出棵数一致）
n = 19（提示上限），dp[19] 仍在 32 位 int 内，无需大数