题目描述：
给你一个整数
n，求恰由n个节点组成且节点值从1到n互不相同的二叉搜索树有多少种？返回满足题意的二叉搜索树的种数。示例 1：
输入：n = 3输出：5示例 2：
输入：n = 1输出：1
解题思路：
方法一：动态规划
核心思路：
状态定义：
dp[i]= 由i个节点组成的二叉搜索树的数量。
状态转移：
对于i个节点，枚举根节点：
根节点左边有
j个节点（构成左子树）根节点右边有
i - 1 - j个节点（构成右子树）
dp[i] = Σ dp[j] × dp[i-1-j]，j 从 0 到 i-1
具体过程示例：
n = 3
dp[0] = 1（空树） dp[1] = 1（1个节点） dp[2] = dp[0]*dp[1] + dp[1]*dp[0] = 1 + 1 = 2 dp[3] = dp[0]*dp[2] + dp[1]*dp[1] + dp[2]*dp[0] = 2 + 1 + 2 = 5 ✅
枚举根节点：
根=1：左0个，右2个 →
dp[0] * dp[2] = 2根=2：左1个，右1个 →
dp[1] * dp[1] = 1根=3：左2个，右0个 →
dp[2] * dp[0] = 2
总计：2 + 1 + 2 = 5 ✅
代码实现：
class Solution { public: int numTrees(int n) { vector<int> dp(n + 1, 0); dp[0] = 1; // 空树 dp[1] = 1; // 1个节点 for (int i = 2; i <= n; i++) { for (int j = 0; j < i; j++) { dp[i] += dp[j] * dp[i - 1 - j]; } } return dp[n]; } };复杂度分析：
| 维度 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n²) | 双重循环 |
| 空间复杂度 | O(n) | dp 数组 |
方法二：卡特兰数
核心思路：
dp[n]就是卡特兰数C_n：
C_n = C(2n, n) / (n + 1)
代码实现：
class Solution { public: int numTrees(int n) { long long result = 1; for (int i = 1; i <= n; i++) { result = result * (n + i) / i; } return result / (n + 1); } };更安全的写法：
class Solution { public: int numTrees(int n) { long long C = 1; for (int i = 0; i < n; i++) { C = C * 2 * (2 * i + 1) / (i + 2); } return (int)C; } };复杂度分析：
| 维度 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n) | 一次循环 |
| 空间复杂度 | O(1) | 只用常数个变量 |
两种方法对比：
| 方法 | 时间复杂度 | 空间复杂度 | 推荐度 |
|---|---|---|---|
| 动态规划 | O(n²) | O(n) | ⭐⭐⭐⭐⭐ |
| 卡特兰数 | O(n) | O(1) | ⭐⭐⭐⭐ |
动态规划更通用（能处理变种），卡特兰数更快但需要知道公式。
关键细节：
1. 为什么dp[0] = 1？
空树也算一种情况。当根节点的左子树或右子树为空时，需要dp[0] = 1来保证乘法正确。
2. 为什么是dp[j] * dp[i-1-j]？
左子树有
j个节点，有dp[j]种结构右子树有
i-1-j个节点，有dp[i-1-j]种结构左右子树独立，所以用乘法
3. 卡特兰数的其他应用
括号匹配数
出栈序列数
凸多边形三角划分
满二叉树计数
总结：
| 要点 | 说明 |
|---|---|
| 核心思想 | 枚举根节点，左右子树独立 |
| 状态转移 | dp[i] = Σ dp[j] × dp[i-1-j] |
| 时间复杂度 | O(n²) |
| 空间复杂度 | O(n) |
