给定 n 个不同值，能构造多少种不同的二叉搜索树？

简化版

不同 BST 数量满足 Catalan 数递推。选择 i 作为根时，左边有 i-1 个值，右边有 n-i 个值，所以 dp[n] = sum(dp[i-1] * dp[n-i])，其中 dp[0]=1。

详细版

对有序值 1..n 构造 BST，关键是根节点一旦选定，左右子树的值域也被确定：

根为 1：左边 0 个，右边 n-1 个；
根为 2：左边 1 个，右边 n-2 个；
根为 i：左边 i-1 个，右边 n-i 个。

左右子树可以独立组合，所以以 i 为根的数量是 dp[i-1] * dp[n-i]。枚举所有根：

dp[0] = 1
dp[1] = 1
dp[n] = Σ dp[left] * dp[right]

时间复杂度 O(n²)，空间复杂度 O(n)。结果是第 n 个 Catalan 数。

完整版教学

一、为什么这题只和数量 n 有关

只要值互不相同，BST 的形状数量只取决于有多少个值，而不取决于具体值是 1..n 还是 [10,20,30]。因为 BST 只关心相对大小：最小值只能出现在某些左链位置，最大值只能出现在某些右侧位置，具体数值大小不会改变结构选择。

所以题目通常把值写成 1..n，本质是在问「n 个有序元素能形成多少种 BST 形状」。这个抽象很重要，否则容易被具体数字干扰。

记忆钩子：BST 计数数的是「有序相对位置」带来的形状，不是数值本身。

二、根节点选择如何拆分问题

如果选 i 作为根，那么小于 i 的 1..i-1 必须都在左子树，大于 i 的 i+1..n 必须都在右子树。左右子树之间没有交叉，形状选择也彼此独立。于是一个大问题被拆成两个规模更小的问题。

例如 n=3：

根	左侧数量	右侧数量	组合数
1	0	2	`dp[0]*dp[2]=2`
2	1	1	`dp[1]*dp[1]=1`
3	2	0	`dp[2]*dp[0]=2`

所以 dp[3]=2+1+2=5。这 5 种就是经典的 3 个节点 BST 形状数。

三、为什么左右子树数量要相乘

以某个根为固定前提，左子树有 A 种形状，右子树有 B 种形状。每一种左形状都可以搭配每一种右形状，因此组合数是 A*B。这就是乘法原理，不是把左右数量相加。

root = i
left choices  = dp[i-1]
right choices = dp[n-i]
total choices under root i = dp[i-1] * dp[n-i]

很多人会误写成 dp[i-1] + dp[n-i]，那只是在二选一，而实际是左右子树同时存在并自由搭配。

四、动态规划代码

dp[k] 表示 k 个不同有序值能构造的 BST 数量。空树 dp[0]=1 是关键，不是 0。因为当某个根没有左子树时，左侧空结构也算 1 种可搭配方案。

int numTrees(int n) {
    int[] dp = new int[n + 1];
    dp[0] = 1;
    dp[1] = 1;
    for (int nodes = 2; nodes <= n; nodes++) {
        for (int left = 0; left < nodes; left++) {
            int right = nodes - 1 - left;
            dp[nodes] += dp[left] * dp[right];
        }
    }
    return dp[n];
}

外层枚举总节点数，内层枚举左子树节点数。根节点占 1 个，所以右子树数量是 nodes - 1 - left。

五、带数字算到 n=4

从小到大算：

dp[0]=1
dp[1]=1
dp[2]=dp[0]dp[1]+dp[1]dp[0]=2
dp[3]=dp[0]dp[2]+dp[1]dp[1]+dp[2]dp[0]=5
dp[4]=1*5 + 1*2 + 2*1 + 5*1 = 14

dp[4]=14，这也是 Catalan 数序列的一项：1,1,2,5,14,42...。面试中不需要背闭式公式，但知道它是 Catalan 数可以帮助你识别同类问题，如括号匹配、出栈序列、不同二叉树形态等。

六、Catalan 数公式和溢出问题

这个递推对应第 n 个 Catalan 数，闭式公式为：

C_n = (1 / (n + 1)) * binom(2n, n)

但在编程题里更常用 DP，因为公式涉及组合数和大整数，容易溢出。若 n 较大，应使用 long、大整数或取模。题目若返回 int，通常 n 的范围会控制在结果不溢出的程度。

n	BST 数量
1	1
2	2
3	5
4	14
5	42

理解递推比死记公式更重要，因为面试更常让你解释「为什么这样转移」。

七、常见误区与追问

误区：根固定后左右子树数量相加。 左右子树是同时选择、自由搭配，应使用乘法原理。
追问：为什么 dp[0] 等于 1？ 空子树是一种合法结构，用来和另一侧子树组合。
误区：具体值不同会改变答案。 只要相对顺序相同，BST 形状数只和节点数量有关。
追问：这和普通二叉树数量有什么关系？ n 个节点的不同二叉树形态也是 Catalan 数，但 BST 用有序值把每个形态唯一标号。
误区：这题必须真的构造所有树。 只问数量时 DP 计数即可，构造所有树会产生指数级结果。

八、加强记忆

这题记住「枚举根，左右相乘，所有根相加」。根把有序值切成左小右大两段；左段有多少种 BST，右段有多少种 BST，二者可以任意搭配，所以乘起来。空树要算 1 种，否则根在边界时组合会被错误清零。看到 1,1,2,5,14 就要联想到 Catalan 数，但面试回答的核心仍然是递推来源。

简化版

详细版