一、题目描述给定整数n要求使用 1 ~ n 这 n 个不同节点 构造所有可能的二叉搜索树BST返回不同 BST 的数量例如示例 1输入n 3输出5对应的五种 BST示例 2输入n 1输出1二、问题本质这道题不是让你构造具体树而是统计有多少种不同结构因此核心问题变成BST 的结构数量如何计算三、二叉搜索树的关键性质BST 满足左子树所有节点 根节点 右子树所有节点 根节点因此如果选择i作为根节点。那么左子树 1 ~ i-1 右子树 i1 ~ n节点数量分别为左子树节点数 i-1 右子树节点数 n-i四、最核心的思想分治假设f(n)表示n 个节点能够构造的 BST 数量如果i 作为根节点那么左子树有f(i-1)种构造方式。右子树有f(n-i)种构造方式。由于左右子树相互独立根据乘法原理当前根节点的 BST 数量 f(i-1) * f(n-i)枚举所有根节点i 1 ~ n所以f(n) Σ f(i-1) * f(n-i)即f(n) f(0)*f(n-1) f(1)*f(n-2) ... f(n-1)*f(0)这就是卡特兰递推公式五、动态规划推导定义dp[i]表示i 个节点构成 BST 的数量状态转移方程dp[i] dp[j-1] * dp[i-j]其中j 表示根节点六、为什么是乘法例如左子树有 2 种 右子树有 3 种那么总方案数 2 × 3 6因为每一种左子树都能和每一种右子树自由组合这是经典组合计数思想。七、边界条件dp[0] 为什么是 1这是本题最容易疑惑的地方。dp[0] 1表示空树也算一种 BST为什么因为例如只有左子树 没有右子树时我们需要左子树方案数 × 空树方案数如果dp[0] 0会导致整个结果变成 0数学上不合理。因此空结构也算一种合法情况dp[1]dp[1] 1只有一个节点只能构造一种 BST八、动态规划代码实现#include iostream #include vector using namespace std; class Solution { public: int numTrees(int n) { vectorint dp(n 1, 0); // 边界条件 dp[0] 1; dp[1] 1; // 计算 dp[i] for (int i 2; i n; i) { // 枚举根节点 for (int j 1; j i; j) { dp[i] dp[j - 1] * dp[i - j]; } } return dp[n]; } };九、完整推导过程n 3dp[0]1dp[1]1dp[2]枚举根根 1左0 个节点右1 个节点方案dp[0] * dp[1] 1 * 1 1根 2左1 个节点右0 个节点方案dp[1] * dp[0] 1 * 1 1因此dp[2] 2dp[3]根 1dp[0] * dp[2] 1 * 2 2根 2dp[1] * dp[1] 1根 3dp[2] * dp[0] 2总和2 1 2 5因此dp[3] 5十、卡特兰数正式登场你会发现1 1 2 5 14 42 132 ...这就是著名的Catalan Number卡特兰数十一、什么是卡特兰数卡特兰数是组合数学中极其经典的一类计数序列。定义C0 1 Cn Σ Ci * C(n-1-i)即Cn C0Cn-1 C1Cn-2 ... Cn-1C0与本题完全一致。十二、卡特兰数经典问题卡特兰数会频繁出现在1. 不同 BST 数量本题。2. 合法括号序列数量例如n 对括号有多少种合法组合3. 出栈序列数量例如n 个元素有多少种合法出栈顺序4. 满二叉树结构数量5. 凸多边形三角划分6. Dyck Path它是算法竞赛中最经典的组合计数之一。十三、卡特兰数通项公式除了 DP还有数学公式C_n \frac{1}{n1}\binom{2n}{n}也可以写成C_n \binom{2n}{n} - \binom{2n}{n-1}十四、为什么会出现卡特兰数因为 BST 的构造过程满足根节点划分左右区间 左右子树递归独立这种递归划分结构是卡特兰数最典型的特征。十五、数学公式代码组合数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; } };十六、为什么动态规划更适合面试虽然公式法更快。但是面试官更关注状态定义 递推关系 分治思想因此DP 解法最推荐因为它体现了问题拆解能力十七、复杂度分析动态规划状态数n每个状态枚举n时间复杂度O(n²)空间复杂度O(n)数学公式时间复杂度O(n)空间复杂度O(1)十八、常见错误总结错误1dp[0] 写成 0这是最经典错误。正确dp[0] 1因为空树也算一种情况错误2左右子树写成加法错误dp[i] dp[left] dp[right]正确dp[i] dp[left] * dp[right]因为左右子树独立组合错误3循环边界错误根节点1 ~ i不要漏掉i