Unique Binary Search Trees 是 LeetCode Hot 100 里面一道非常经典的动态规划题。
这道题非常有代表性，因为它表面上是在问“由 1...n 组成的二叉搜索树有多少种不同结构”，但本质上考察的是：
-
如何把一棵树拆成左右子树
-
如何把“结构数量统计”写成递推
-
两种思路：
-
递归 + 记忆化搜索
-
卡特兰数公式
这两种写法都对，而且它们不是互相独立的。 更准确地说：
递归 / DP 是理解题目结构的过程，卡特兰数是把这个结构进一步抽象后的更简洁写法。
所以这篇文章我就按这个顺序来讲。
题目介绍
给定一个整数 n，要求你统计：
由 1 到 n 这 n 个节点组成的二叉搜索树，一共有多少种不同的结构。
注意是“结构不同”的二叉搜索树数量，而不是遍历顺序，也不是随便二叉树。
二叉搜索树满足：
-
左子树所有节点值都小于根节点
-
右子树所有节点值都大于根节点
例如当 n = 3 时，节点值为：
1, 2, 3
它们一共可以组成 5 种不同的二叉搜索树，所以答案是：
5
最关键的观察
这道题最核心的一步，是去思考：
如果固定某个数字作为根节点，那么左右子树还能有多少种构造方法？
假设选数字 i 作为根节点，那么：
-
左子树只能由
1 ... i-1这些数字组成，一共i-1个节点 -
右子树只能由
i+1 ... n这些数字组成，一共n-i个节点
而且：
-
左子树怎么构造，和右子树怎么构造，是彼此独立的
-
所以如果左子树有
L种构造方式，右子树有R种构造方式 -
那么当前根节点对应的总数就是：
L × R
最后再把所有根节点的情况加起来，就是总答案。
这就是整道题最本质的递推来源。
解法一：递归 + 记忆化搜索
你图片里的写法，本质上是在做这件事：
定义：
numTrees(n) = 用 n 个节点能组成的不同二叉搜索树数量
那么递归关系就是：
numTrees(n) = Σ numTrees(i-1) * numTrees(n-i) （i 从 1 到 n）
其中：
-
i表示当前选哪个数当根 -
i-1是左子树节点数 -
n-i是右子树节点数
为什么要记忆化？
因为在递归过程中，会反复计算很多相同的子问题。
比如：
-
numTrees(2)可能会被多次用到 -
numTrees(3)也可能会被反复求
所以图片里的代码用了一个缓存数组 nums[]，把算过的结果存起来。 下次再遇到同样的 n，就直接返回，不再重复递归。
这就是典型的 记忆化搜索。
核心逻辑
可以概括成下面几步：
1. 边界情况
n = 0 时，返回 1
这里的 1 表示“空树也算一种结构”。
这个定义非常重要。因为如果某个根节点一边子树为空，我们仍然希望组合数公式成立。
2. 如果缓存里已经有结果，直接返回
避免重复计算。
3. 枚举每一个数字作为根节点
对于每个根节点 i：
-
左子树数量 =
numTrees(i - 1) -
右子树数量 =
numTrees(n - i)
然后把：
left × right
累加起来。
4. 把结果存进缓存
以后可以直接复用。
为什么这种写法是对的？
因为它完整体现了这道题的结构拆分：
-
根节点一旦确定
-
左子树和右子树的节点数量也随之确定
-
左右子树的构造方案彼此独立，所以要相乘
-
所有根节点情况都要考虑，所以最后求和
而缓存的加入，只是为了避免重复计算，并不改变递推本质。
所以图片里的解法，本质上其实就是：
递归版动态规划
它特别适合理解这道题为什么能递推。
进一步抽象：动态规划写法
如果把记忆化搜索改写成更经典的 DP 数组形式，就会得到：
设：
dp[k] = k 个节点能组成的不同 BST 数量
那么状态转移方程就是：
dp[n] = Σ dp[i-1] * dp[n-i]
初始条件：
dp[0] = 1
dp[1] = 1
例如：
dp[3] = dp[0]*dp[2] + dp[1]*dp[1] + dp[2]*dp[0]
如果：
dp[0] = 1
dp[1] = 1
dp[2] = 2
那么：
dp[3] = 1*2 + 1*1 + 2*1 = 5
这正好就是答案。
所以你图片里的递归写法，和标准 DP，其实本质完全一样。
解法二：卡特兰数
class Solution {
public int numTrees(int n) {
long res = 1;
for (int i = 0; i < n; i++) res = res * 2 * (2 * i + 1) / (i + 2);
return (int) res;
}
}
这段代码没有显式写出 dp 数组，但它其实是在直接计算：
第 n 个卡特兰数
因为这道题的答案，恰好就是卡特兰数。
卡特兰数在这题里的来源，其实就是刚才那个递推：
dp[n] = Σ dp[i-1] * dp[n-i]
这个递推，正是卡特兰数最经典的定义型递推之一。
也就是说：
-
你图片里的思路，帮我们理解了为什么答案满足这种递推
-
卡特兰数公式，则是把这个递推进一步压缩成更简洁的数学实现
卡特兰数公式为什么能这样写？
卡特兰数常见递推形式之一是：
C0 = 1
Cn+1 = Cn * 2 * (2n + 1) / (n + 2)
而你的代码正是在按这个公式递推。
从 C0 = 1 开始，不断向后推到 Cn：
long res = 1;
for (int i = 0; i < n; i++) {
res = res * 2 * (2 * i + 1) / (i + 2);
}
最后得到的 res，就是答案。
这种写法的优点非常明显：
-
不需要显式开
dp数组 -
不需要写双层循环
-
时间复杂度降到
O(n) -
空间复杂度降到
O(1)
所以它是理解题目本质之后，一个非常漂亮的优化写法。
手动模拟一遍
我们用 n = 3 来看。
已知：
C0 = 1
第一次循环：i = 0
res = 1 * 2 * 1 / 2 = 1
得到：
C1 = 1
第二次循环：i = 1
res = 1 * 2 * 3 / 3 = 2
得到：
C2 = 2
第三次循环：i = 2
res = 2 * 2 * 5 / 4 = 5
得到：
C3 = 5
所以最终答案就是：
5
这正好和题目要求一致。
两种解法怎么理解它们的关系？
这题最值得掌握的，其实不是只会写某一种代码，而是理解这三层关系：
第一层：递归结构
枚举根节点，左右子树独立，相乘再求和。
第二层：动态规划 / 记忆化
把重复子问题缓存起来，避免反复计算。
第三层：卡特兰数
进一步发现这个递推其实就是卡特兰数，于是可以直接套更简洁的数学递推公式。
所以真正完整的理解顺序应该是：
先看懂递归结构，再接受 DP，最后认识到它其实就是卡特兰数。
复杂度分析
解法一：递归 + 记忆化 / DP
如果写成标准 DP：
-
时间复杂度：
O(n^2)
因为每个 dp[i] 都要枚举一次根节点。
-
空间复杂度：
O(n)
解法二：卡特兰数公式
你最终代码的复杂度更优：
-
时间复杂度：
O(n)
-
空间复杂度：
O(1)
所以从实现效率上来说，卡特兰数写法更强； 但从理解题目结构来说，递归 / 记忆化写法更适合讲清楚“为什么”。
总结
这道题的核心思想可以概括成一句话：
固定每个数字作为根节点时，左右子树的节点数量就确定了，而左右子树方案数彼此独立，因此总数满足“左右相乘、对所有根求和”的递推关系。
所以这题可以分成两层理解：
解法一：递归 + 记忆化搜索
核心递推：
numTrees(n) = Σ numTrees(i-1) * numTrees(n-i)
这是理解题目结构最自然的方式。
解法二：卡特兰数公式
最终实现：
class Solution {
public int numTrees(int n) {
long res = 1;
for (int i = 0; i < n; i++) res = res * 2 * (2 * i + 1) / (i + 2);
return (int) res;
}
}
这是在看懂递推本质之后，更简洁、更优雅的实现。
这道题非常经典，因为它会让你真正体会到：
-
树形结构如何拆成子问题
-
动态规划如何从递归中长出来
-
数学公式又如何进一步把 DP 压缩掉
把这道题真正吃透之后，再去看：
-
括号生成
-
不同的二叉搜索树 II
-
卡特兰数相关题目
你会更容易意识到： 很多题表面不同，但它们背后统计的其实是同一种结构。
