好的，我们接下来讲解 LeetCode 第 96 题「不同的二叉搜索树」。

题目描述

给你一个整数 n，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 (BST) 有多少种？返回满足题意的二叉搜索树的种数。

示例：

输入：n = 3
输出：5
解释：当 n=3 时，共有 5 种不同结构的二叉搜索树。

循序渐进讲解

第一步：理解题意与二叉搜索树的性质

二叉搜索树的特点是：

• 左子树的所有节点值 < 根节点值
• 右子树的所有节点值 > 根节点值
• 左右子树也都是二叉搜索树

题目要求：给定节点数 n，计算不同结构的 BST 数量（节点值从 1 到 n，结构不同即视为不同，与具体节点值无关，只与相对大小关系有关）。

第二步：从具体例子找规律

先看小例子：

• n = 0：空树，算 1 种。

• n = 1：只有根节点，1 种。

• n = 2：

  • 根为 1，右子树 1 个节点（2）：1 种
  • 根为 2，左子树 1 个节点（1）：1 种
  • 总共 = 2 种

• n = 3：

  • 根为 1：右子树有 2 个节点（2,3），右子树结构数 = n=2 时的结果 = 2
  • 根为 2：左子树 1 个节点（1），右子树 1 个节点（3），结构数 = 1×1 = 1
  • 根为 3：左子树 2 个节点（1,2），结构数 = n=2 时的结果 = 2
  • 总共 = 2 + 1 + 2 = 5

发现规律：以某个数 i 为根时：

• 左子树由 1 ... i-1 组成，节点数 = i-1
• 右子树由 i+1 ... n 组成，节点数 = n-i
• 左右子树结构数相乘，即为以 i 为根的 BST 数量。

第三步：定义递归关系（动态规划思路）

设 G(n) 表示 n 个节点能构成的 BST 种数。

枚举根节点 i（从 1 到 n）：

• 左子树节点数 = i-1，结构数 = G(i-1)
• 右子树节点数 = n-i，结构数 = G(n-i)
• 以 i 为根的 BST 数量 = G(i-1) × G(n-i)

所以：

G(n) = Σ [G(i-1) × G(n-i)]  对 i=1 到 n 求和

其中 G(0) = 1（空树），G(1) = 1。

这就是 卡特兰数 (Catalan Number) 的递推公式。

第四步：动态规划计算

用数组 dp 存储结果：

• dp[0] = 1
• dp[1] = 1
• 对于 n >= 2：

  dp[n] = 0
  for i in 1..n:
      dp[n] += dp[i-1] * dp[n-i]
  

计算过程示例：

n=0: dp[0] = 1
n=1: dp[1] = dp[0]*dp[0] = 1
n=2:

• i=1: dp[0]*dp[1] = 1×1 = 1
• i=2: dp[1]*dp[0] = 1×1 = 1
  dp[2] = 1+1 = 2

n=3:

• i=1: dp[0]*dp[2] = 1×2 = 2
• i=2: dp[1]*dp[1] = 1×1 = 1
• i=3: dp[2]*dp[0] = 2×1 = 2
  dp[3] = 2+1+2 = 5

n=4:

• i=1: dp[0]*dp[3] = 1×5 = 5
• i=2: dp[1]*dp[2] = 1×2 = 2
• i=3: dp[2]*dp[1] = 2×1 = 2
• i=4: dp[3]*dp[0] = 5×1 = 5
  dp[4] = 5+2+2+5 = 14

第五步：算法实现（伪代码）

def numTrees(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]

时间复杂度：O(n²)
空间复杂度：O(n)

第六步：进阶理解（卡特兰数公式）

这个数列就是卡特兰数：

C(n) = (2n)! / ( (n+1)! n! )

也可写作：

C(n) = C(2n, n) / (n+1)

其中 C(2n, n) 是组合数。

例如 n=3:
C(3) = 6! / (4! × 3!) = 720 / (24×6) = 720/144 = 5

可以直接用公式计算，时间复杂度 O(n) 或 O(1)（若预先计算阶乘）。

总结

这道题的关键是理解：

1. 二叉搜索树的结构只与节点数有关。
2. 固定根节点后，问题分解为左子树和右子树的子问题。
3. 利用动态规划避免重复计算，得到卡特兰数序列。

这样，我们就得到了计算 n 个节点能构成的不同二叉搜索树数量的方法。