96. 不同的二叉搜索树
题目描述
给你一个整数 n，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例
示例 1：
输入：n = 3
输出：5
示例 2：
输入：n = 1
输出：1
解题思路
第一步：理解问题本质
二叉搜索树的性质：左子树所有节点 < 根 < 右子树所有节点。关键问题是：给定 n 个节点，能构造多少种不同的 BST？
第二步：动态规划
核心洞察：
G(n)表示n个节点能构成的不同 BST 的个数- 对于根节点
i，左子树有i-1个节点，右子树有n-i个节点 G(n) = sum(G(i-1) * G(n-i))foriin1..n
为什么正确：
- 选定根节点
i后，左子树只能是[1, i-1]，右子树只能是[i+1, n] - 左右子树互相独立，用乘法原理
完整代码实现
class Solution:
"""
不同的二叉搜索树 - 动态规划（卡特兰数）
G(n) = sum(G(i-1) * G(n-i)) for i in 1..n
时间复杂度：O(n²)
空间复杂度：O(n)
"""
def numTrees(self, n: int) -> int:
G = [0] * (n + 1)
G[0], G[1] = 1, 1
for i in range(2, n + 1):
for j in range(1, i + 1):
G[i] += G[j - 1] * G[i - j]
return G[n]
示例推演
以 n = 3 为例：
| 根节点 | 左子树节点数 | 右子树节点数 | G(左) | G(右) | 组合数 |
|---|---|---|---|---|---|
| 1 | 0 | 2 | 1 | 2 | 2 |
| 2 | 1 | 1 | 1 | 1 | 1 |
| 3 | 2 | 0 | 2 | 1 | 2 |
总数：2 + 1 + 2 = 5
卡特兰数：1, 1, 2, 5, 14, 42, 132, ...
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 暴力递归 | O(2^n) | O(n) | 大量重复计算 |
| DP（最优） | O(n²) | O(n) | 递推计算 |
易错点总结
1. G(0) = 1
空树也算一种 BST，所以 G[0] = 1。