题目描述给你一个整数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 3dp[0] 1空树 dp[1] 11个节点 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) { vectorint 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_nC_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)
