不同的二叉搜索树 图解题解

这道题数的是什么，为什么只看形状

题目给整数 n，节点值固定是 1 到 n，问能组成多少种结构不同的二叉搜索树（BST，左子树全小于根、右子树全大于根的二叉树）。听起来要同时考虑「放哪些值」和「长什么形状」，其实只需要数形状。原因藏在 BST 的一条性质里：它的中序遍历必然是升序，也就是恒为 1 到 n。这意味着给定一种树的形状，把 1 到 n 按中序位置填进去的方式是唯一的——形状定了，每个节点放谁就定了。所以答案只跟节点个数有关，跟具体取哪些值无关。

为什么想到枚举根来分解问题

直接枚举所有树形是不现实的，树形数量增长极快。突破口是 BST 的结构约束：一旦选定某个数 k 当根，比 k 小的数必须全部进左子树、比 k 大的数必须全部进右子树，两边各是多少个节点就完全确定了。整棵树的问题被根一刀切成两个更小的同类问题。

更关键的是，由上一节的结论，子树的方案数只取决于节点个数。左边有 j 个节点，不管这 j 个具体是哪些值，能搭出的形状数都一样。于是「n 个节点的 BST 数」可以由「更少节点的 BST 数」推出来——这正是动态规划要的递推结构。

dp 怎么定义，为什么左右方案数是相乘

定义 dp[i] 为 i 个节点能组成的结构不同的 BST 个数。计算 dp[i] 时枚举根：让第 k 个数当根，左子树分到 j = k-1 个节点、右子树分到 i-1-j 个。左子树有 dp[j] 种搭法，右子树有 dp[i-1-j] 种，左右两边互不干扰、可以自由组合，按乘法原理这一种根贡献 dp[j] × dp[i-1-j] 种树。

不同的根产生的树根节点不同，绝不会重复，按加法原理把 i 种根的贡献全部加起来，就是 dp[i] = Σ dp[j] × dp[i-1-j]，j 从 0 取到 i-1。这里最容易犯的错是把左右子树的方案数加起来——加法数的是「二选一」，而左右子树是同时存在、独立各选一种，必须相乘。

dp[0] 为什么必须等于 1 而不是 0

空树也算一种合法形态：根没有左孩子时，左子树就是空树，这种情况实实在在贡献着方案。dp[0] 在递推式里始终以乘数身份出现，比如最小的数当根时贡献是 dp[0] × dp[i-1]，若 dp[0] 设成 0，所有单边为空的树会被整体乘没，dp[1] 都算不出来。把 dp[0] 定为 1，读作「空树恰有一种形态」，整个递推才立得住。

从 dp[0]=1、dp[1]=1 出发依次递推，得到 2、5、14、42、132、429、1430……n=8 时答案就是 1430。

复杂度多少，和卡特兰数是什么关系

时间复杂度 O(n²)：外层 i 从 1 递推到 n，内层枚举 i 个根。空间 O(n)，一维 dp 数组。

dp[i] = Σ dp[j] × dp[i-1-j] 正是卡特兰数的递推式，所以 dp[n] 就是第 n 个卡特兰数，有封闭公式 C(2n,n)/(n+1)。合法括号序列、出栈顺序等经典计数问题与本题同构，面试里能点出这一层，说明你看到的不只是一道题，而是一类「枚举分割点、左右相乘再求和」的计数结构。

Python

def numTrees(n):
    dp = [0] * (n + 1)
    dp[0] = 1
    for i in range(1, n + 1):
        for j in range(i):          # 左子树节点数
            dp[i] += dp[j] * dp[i - 1 - j]
    return dp[n]

C++

int numTrees(int n){
    vector<int> dp(n + 1, 0);
    dp[0] = 1;
    for(int i = 1; i <= n; ++i)
        for(int j = 0; j < i; ++j)
            dp[i] += dp[j] * dp[i - 1 - j];
    return dp[n];
}

Java

int numTrees(int n){
    int[] dp = new int[n + 1];
    dp[0] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = 0; j < i; j++)
            dp[i] += dp[j] * dp[i - 1 - j];
    return dp[n];
}