96. 不同的二叉搜索树

题目链接（中等）

题目描述

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

数据范围：

• 1 <= n <= 19

示例

示例 1：

输入： n = 3
输出： 5

示例 2：

输入： n = 1
输出： 1

方法一：动态规划

思路及解法

给定有序序列 1, 2, ..., n，任选一个数 i 作为根节点，那么：

• 左子树由 1, ..., i-1 构成；
• 右子树由 i+1, ..., n 构成；
• 左右子树递归地构建，且都必须是二叉搜索树。

关键观察：二叉搜索树的种数只和序列的长度有关，和具体数值无关。因此可以定义：

• G(n)：长度为 n 的序列能构成的不同二叉搜索树的个数（这就是答案）；
• F(i, n)：以 i 为根、序列长度为 n 的不同 BST 个数。

所有可能的根都要枚举，所以：

[
G(n) = \sum_{i=1}^{n} F(i, n)
]

而以 i 为根时，左子树有 i-1 个节点，右子树有 n-i 个节点，两者独立组合（笛卡尔积），因此：

[
F(i, n) = G(i-1) \cdot G(n-i)
]

代入得到 G(n) 的递归式（即卡特兰数的递推公式）：

[
G(n) = \sum_{i=1}^{n} G(i-1) \cdot G(n-i)
]

边界条件：

• G(0) = 1（空树，算一种）；
• G(1) = 1（只有一个根节点）。

直觉理解：G(n) 表示 n 个节点能组成多少种 BST。选定根之后，问题就拆成了两个规模更小的子问题（左子树和右子树的种数），相乘再对所有可能的根求和。

因为 G(n) 只依赖 G(0) ... G(n-1)，所以从小到大递推计算即可。

举例：n = 3

• G(0) = 1，G(1) = 1；
• G(2) = G(0)·G(1) + G(1)·G(0) = 1 + 1 = 2；
• G(3) = G(0)·G(2) + G(1)·G(1) + G(2)·G(0) = 2 + 1 + 2 = 5。

代码

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[0], dp[1] = 1, 1

        for num_n in range(2, n+1):
            for i in range(1, num_n + 1):
                dp[num_n] += dp[i - 1] * dp[num_n - i]
        
        return dp[n]

复杂度分析

• 时间复杂度：$O(n^2)$，共 n 个状态，每个状态需要枚举 j 求和。
• 空间复杂度：$O(n)$，G 数组长度为 n + 1。

方法二：数学（卡特兰数）

思路及解法

方法一推出的递推公式正是卡特兰数：

[
C0 = 1, \quad C{n+1} = \frac{2(2n+1)}{n+2} \cdot C_n
]

卡特兰数的通项公式为：

[
C_n = \frac{1}{n+1} \binom{2n}{n} = \frac{(2n)!}{(n+1)!\,n!}
]

因此可以只用一个变量，按递推公式计算：

C = 1
for i in range(n):
    C = C * 2 * (2 * i + 1) // (i + 2)

注意用整除 //，因为每一步乘积都能保证整除（卡特兰数的性质），不会丢失精度。

代码

class Solution:
    def numTrees(self, n: int) -> int:
        C = 1
        for i in range(n):
            C = C * 2 * (2 * i + 1) // (i + 2)
        return C

复杂度分析

• 时间复杂度：$O(n)$，只需一次循环。
• 空间复杂度：$O(1)$，只需常数个变量。