不同的二叉搜索树 图解题解
这道题到底在问什么
- 输入 n
- 3
- 输出
- 5
先想最直接的笨办法
dp[4] 枚举 4 个根，每个根的左右点数加起来都是 3，凑出 14。dp[5] 同理得 42。每个新格只用到左边已经填好的格，所以从小到大一路填下去就行。1、1、2、5、14、42 这串数，就是著名的卡特兰数。（动画第 14 步）
最优解：一步一步想明白
- 3先画根选 2 这棵：1 在左、3 在右，左右各一个点。根选 1 的、根选 3 的还有好几棵——不逐棵画，后面用 DP 直接把总数 5 数出来。
- 4想真的把每棵树都摆出来再数，数量随 n 暴涨，n 大一点就画不动了。题目只问数量，我们不该去构造，要去算。
- 5关键观察：BST 里数值是有序的。一旦定下谁当根，比它小的全在左子树、比它大的全在右子树，左右各有几个点就被锁死了。
- 6把 1、2、3 摆成一排。手指点在 2 上当根，它左边天然只剩 1 个数、右边只剩 1 个数——位置一选，左右的「点数」立刻确定，跟具体是哪个数无关。
- 7手指挪到最左的 1。它左边一个数都没有（0 个点），右边剩 2 个点。于是问题变成：左边 0 个点能搭几棵 × 右边 2 个点能搭几棵。这就把大问题拆成了两个更小的同类问题。
- 8再关键一步：3 个连续数和 30、31、32 这三个数，搭出的 BST 形状数完全一样——只跟「点的个数」有关。所以定义 dp[k] 等于 k 个点能搭多少棵 BST，左右子树都能直接复用它。
- 9dp[0] 必须等于 1。空子树不是「没有」，它是一种合法形态——当某个根没有左孩子时，左边那一半就贡献「1 种」。这一格写错，整张表全塌。dp[1] 自然是 1。
- 102 个点。第一个数当根：左 0 个右 1 个，dp[0]×dp[1]=1。第二个数当根：左 1 个右 0 个，dp[1]×dp[0]=1。两种根各一种树，加起来 dp[2]=2。注意是「左 × 右」相乘，再把每个根的结果「相加」。
- 113 个点，先让最小的数当根。它左边 0 个点（dp[0]=1）、右边 2 个点（dp[2]=2），相乘得 2 种。这一项还没写进 dp[3]，先记着。
- 12换中间的数当根，左右各 1 个点，dp[1]×dp[1]=1 种。注意右边那 1 个点和左边那 1 个点，搭出的形状数都是 dp[1]，跟具体数值无关——这正是只看个数的好处。
- 13最后让最大的数当根，左 2 个右 0 个，dp[2]×dp[0]=2。把三个根的结果加起来：2+1+2=5，写进 dp[3]。这就是样例 n=3 的答案 5。
- 14dp[4] 枚举 4 个根，每个根的左右点数加起来都是 3，凑出 14。dp[5] 同理得 42。每个新格只用到左边已经填好的格，所以从小到大一路填下去就行。1、1、2、5、14、42 这串数，就是著名的卡特兰数。
- 17一句话本质：固定一个根，左右两半互不干扰，方案数相乘；换不同的根方案数相加。这就是计数 DP 的母题套路。
- 19常见错觉：以为答案是 1、2、3 的排列数 3 的阶乘等于 6。错在哪？排列数数的是「插入顺序」、BST 数的是「形状」——比如 2、1、3 和 2、3、1 两种顺序长出的是同一棵树（根 2、左 1、右 3），多种顺序会塌成同一形状。两者没有简单加减关系：n=3 碰巧是 6 与 5，到 n=4 就是排列 24、形状只有 14，差距迅速拉大。千万别用排列数去估形状数。
- 24学会这招后去迁移：LC95 把计数换成构造、矩阵链乘 / 戳气球（LC312）也是枚举「最后处理谁」再把区间一拆两半。点开 DP 专题或问问 AI 助教「还有哪些题是枚举分割点」，连成一串。
⚠️ 容易写错的地方
✗ 错：dp[0] 忘了设成 1
✓ 对：空树必须算一种方案
根在最左或最右时，有一侧是空子树，乘上 dp[0]。dp[0]=0 会把整项乘成 0，答案全错
✗ 错：左右点数写成 root 和 nodes-root
✓ 对：应是 root-1 和 nodes-root
根节点自己要从点数里扣掉，左边是 root-1 个、右边才是 nodes-root 个
✗ 错：大 n 用 int 存 dp
✓ 对：C++/Java 用 long
卡特兰数增长很快，n=19 就接近 int 上限，会悄悄溢出成负数
完整代码（Python / C++ / Java）
Python
class Solution:
def numTrees(self, n: int) -> int:
dp = [0] * (n + 1)
dp[0] = 1 # 空树算一种
for nodes in range(1, n + 1):
for root in range(1, nodes + 1):
left = root - 1 # 左子树点数
right = nodes - root # 右子树点数
dp[nodes] += dp[left] * dp[right]
return dp[n]C++
class Solution {
public:
int numTrees(int n) {
vector<long long> dp(n + 1, 0);
dp[0] = 1; // 空树算一种
for (int nodes = 1; nodes <= n; ++nodes)
for (int root = 1; root <= nodes; ++root) {
int left = root - 1; // 左子树点数
int right = nodes - root; // 右子树点数
dp[nodes] += dp[left] * dp[right];
}
return (int)dp[n];
}
};Java
class Solution {
public int numTrees(int n) {
long[] dp = new long[n + 1];
dp[0] = 1; // 空树算一种
for (int nodes = 1; nodes <= n; nodes++)
for (int root = 1; root <= nodes; root++) {
int left = root - 1; // 左子树点数
int right = nodes - root; // 右子树点数
dp[nodes] += dp[left] * dp[right];
}
return (int) dp[n];
}
}套路模板 · 枚举分割点计数（可背骨架）
# 计数型区间 DP 通用骨架
dp = [0] * (n + 1)
dp[0] = 1 # 空区间 = 1 种基底
for size in range(1, n + 1): # 枚举区间长度
for split in range(size): # 枚举谁当分割点/根
left = split # 左半点数
right = size - 1 - split # 右半点数（扣掉分割点）
dp[size] += dp[left] * dp[right]
return dp[n]// 计数型区间 DP 通用骨架
vector<long long> dp(n + 1, 0);
dp[0] = 1; // 空区间 = 1 种基底
for (int size = 1; size <= n; ++size)
for (int split = 0; split < size; ++split) {
int left = split; // 左半点数
int right = size - 1 - split; // 右半点数
dp[size] += dp[left] * dp[right];
}
return (int)dp[n];// 计数型区间 DP 通用骨架
long[] dp = new long[n + 1];
dp[0] = 1; // 空区间 = 1 种基底
for (int size = 1; size <= n; size++)
for (int split = 0; split < size; split++) {
int left = split; // 左半点数
int right = size - 1 - split; // 右半点数
dp[size] += dp[left] * dp[right];
}
return (int) dp[n];复杂度
时间复杂度
O(n²)
外层 n 个规模，内层每个规模最多枚举 n 个根
空间复杂度
O(n)
只存一维 dp 数组
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 不同的二叉搜索树 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这串数是卡特兰数吗？有没有公式 O(n) 算？+
是。卡特兰数有递推式 C(n) = C(n-1)·(4n-2)/(n+1)，一遍循环 O(n) 就能算出，比 O(n²) DP 更快。面试讲清 DP 推导即可，能补一句公式更亮眼。
如果不只要数量，还要真把每棵树构造出来呢？+
那就是 LC95「不同的二叉搜索树 II」。把「点数相乘」换成「真的递归生成左右子树列表，再两两拼接挂到根上」，思路同源、实现升级。
为什么左右子树能直接复用 dp，不用管具体是哪几个数？+
BST 的形状只取决于节点的相对大小关系，跟具体数值无关。k 个连续数和任意 k 个不同数，搭出的形状种类完全一样，所以统一记成 dp[k]。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。