1. 简介
二叉树 是一种每个节点最多有两个子节点的分层数据结构。而 二叉搜索树 (BST) 是一种更具体的二叉树，其主要特性是它保持排序顺序。因此，只有当对二叉树进行 中序遍历 后得到一个有序序列时，该二叉树才是 BST。
本文将介绍如何根据树中节点数量，计算可能的二叉搜索树（BST）结构数量。
2. BST 结构的唯一数量
在 BST 中，每个节点包含一个可排序的键。例如，我们可以用整数为每个节点打标签。因此，在 BST 中，每个节点的键值都大于等于其左子树中的任意键值，小于等于其右子树中的任意键值。
给定一组 
个互不相同的数字，我们想计算由这些数字标记的 BST 的数量。不失一般性，我们可以假设这些数字是 
。
例如，对于数字 1, 2, 3，共有 5 种可能的 BST：
当 较小时，我们可以手动枚举所有可能的树结构。但随着 增大，BST 数量迅速增长。例如，当 
时，共有 
种结构。因此，我们需要通过算法来计算这个数量。
3. 递归方法
设 
表示 n 个不同节点能构成的 BST 总数。
对于一组 个不同数字，我们可以任选其中一个作为根节点。例如，我们选择 
作为根节点，则 ![1, 2, ..., i-1] 构成左子树，![i+1, ..., n] 构成右子树。
左子树有 
种结构，右子树有 
种结构。两者独立，因此以 i 为根的 BST 数量为：
$$ f(i-1) \times f(n-i) $$
遍历所有可能的根节点，我们得到递推公式：
$$ f(n) = \sum_{i=1}^{n} f(i-1) \times f(n-i) $$
边界条件为：当没有节点时（即 n=0），只有一种结构（空树），即：
$$ f(0) = 1 $$
基于这个递推式，我们可以写出递归算法：
int countBSTRecursive(int n) {
if (n == 0) return 1;
int result = 0;
for (int i = 1; i <= n; i++) {
result += countBSTRecursive(i - 1) * countBSTRecursive(n - i);
}
return result;
}
✅ 优点：逻辑清晰，易于理解
❌ 缺点：存在大量重复计算，时间复杂度高（指数级）
4. 动态规划方法
递归方法存在大量重复计算，我们可以使用动态规划优化，提前计算并缓存中间结果。
设 dp[i] 表示 i 个节点能组成的 BST 数量。初始化 dp[0] = 1，然后按递推式依次计算 dp[1] 到 dp[n]。
int countBSTDP(int n) {
int[] dp = new int[n + 1];
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 dp[n];
}
✅ 优点：避免重复计算，时间复杂度为 O(n²)
⚠️ 注意：空间复杂度 O(n)，适合 n 不太大（如 ≤ 1000）
5. Catalan 数方法
BST 的数量实际上是 Catalan 数 的第 n 项：
$$ C_n = \frac{1}{n+1} \binom{2n}{n} $$
但我们不需要计算阶乘，可以使用递推公式：
$$ C_0 = 1, \quad C_{n+1} = \sum_{i=0}^{n} C_i \cdot C_{n-i} $$
这个递推式和前面的 BST 数量公式一致。因此，我们可以直接使用 Catalan 数公式计算：
int countBSTCatalan(int n) {
long C = 1;
for (int i = 1; i <= n; i++) {
C = 2 * (2 * i + 1) * C / (i + 2);
}
return (int) C;
}
✅ 优点：时间复杂度 O(n)，效率高
⚠️ 注意：使用 long 避免整数溢出
6. 总结
| 方法 | 时间复杂度 | 适用场景 | 说明 |
|---|---|---|---|
| 递归 | 指数级 | 小规模 n | 逻辑清晰但效率低 |
| 动态规划 | O(n²) | 中等规模 n | 更直观，适合理解 BST 结构 |
| Catalan 数 | O(n) | 大规模 n | 最快方法，适合性能要求高场景 |
✅ 推荐：对于大规模数据，优先使用 Catalan 数方法；若需要理解结构关系，使用动态规划更直观。
⚠️ 踩坑提醒：Catalan 数公式计算时要注意类型溢出，建议使用 long 类型。