刷题平台上编号 96 的“不同的二叉搜索树”，单看标题像是在考树的遍历或者递归构造，可真动手做过的朋友应该都有同感：这题压根不是树的题，它是组合数学的题，核心叫做卡特兰数。第一次见到这题的时候，我的第一反应也是老老实实把 n 个节点的所有二叉搜索树都构造出来再数一遍，写一半就放弃了——n 到 19，树形数量早就突破千万级别，递归枚举连单测都跑不完。后来想明白一个道理：题目不要求你列出每一棵树，只要求说出有多少棵，那么任何一棵树的内部结构细节都不重要，重要的是“怎么从子问题的规模推算出母问题的规模”。这篇文章就把这条思路完整走一遍，从递推公式到卡特兰数，再到代码里容易踩的边界和溢出问题，适合所有刷题遇到这道题的人，也适合想搞懂 DP 计数问题底层逻辑的读者。
1. 题目到底在问什么：先拆穿二叉搜索树的伪装
1.1 关键词是“不同”，不是“搜索”
先看题意：给定一个整数 n，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的二叉搜索树有多少种。注意两个限定条件：二叉搜索树、值从 1 到 n。
题目里的“不同”到底不同在哪？它指的是树的结构不同，也就是左右子树的形态不一样。节点值虽然各不相同，但 BST 的规则（左小右大）会把值的相对顺序固定下来，真正能变的只有树的分叉结构。我们验证一下：
n=1，只可能是一棵单节点树，答案 1。 n=2，值 1、2。可以以 1 为根，右子树放 2；也可以以 2 为根，左子树放 1。答案 2。 n=3，值 1、2、3。以 1 为根时，右子树由 {2,3} 组成，2 和 3 可以组成 2 种 BST 形态；以 2 为根时，左右各一个单节点，1 种；以 3 为根时，左子树由 {1,2} 组成，也是 2 种。加起来 5 种。
这其实就是后面递推公式的雏形，但先别急，我们先理解结构本身。
1.2 根节点一旦选定，左右子树就是两个独立的小问题
BST 的性质是：任意节点的左子树所有值都小于它，右子树所有值都大于它。把这个性质套到整棵树上：如果我选择值 i 作为根节点，那么左子树只能从 {1, 2, ..., i-1} 里选节点，右子树只能从 {i+1, i+2, ..., n} 里选节点。
这句话看起来是废话，其实它是整道题的分水岭。想通它，递推就是水到渠成。因为左子树的节点数量是 i-1，右子树的节点数量是 n-i，左右两棵子树各自都是一棵独立的二叉搜索树，它们的计数分别就是“i-1 个节点的 BST 数量”和“n-i 个节点的 BST 数量”。注意这里用到的只有节点数量，节点值具体从多少到多少根本无所谓——{1,2,3} 能构成的 BST 形态和 {6,7,8} 能构成的 BST 形态在数量上完全一样，只是把值换个名字。这个“只关数量、不关具体值”的观察，是所有子树计数问题的通用钥匙。
2. 从暴力枚举到递推公式：核心观察是怎么来的
2.1 暴力构造为什么必然失败
最容易想到的办法：递归生成所有满足条件的 BST，放到集合里数个数。n 小的时候（比如 n<=4）没问题，可一旦 n 稍大就崩了。一个 n=19 的 BST 形态数是 1767263190，超过 17 亿，就算每棵树只占 1 个字节，你也得准备 1.7GB 内存，而实际上每棵树的描述远不止 1 个字节。这个方向毫无疑问是死路。
于是自然转向计数：我不需要列出树，只需要算出树的数量。既然根的取值有 n 种，每种取值把问题切成左右两个子问题，而左右子树的形态组合是任意的，那么总数量就可以用子问题的答案算出来。这就是动态规划的路子，本质上也就是把暴力枚举做了“合并同类项”。
2.2 递推公式：dp[n] = Σ dp[i-1] * dp[n-i]
定义 dp[k] 表示 k 个节点能组成的 BST 数量。初始 dp[0]=1（空树也是一种合法形态，后面会看到它有多重要），dp[1]=1。对于任意的 n，枚举根节点取值 i（i 从 1 到 n），左子树有 i-1 个节点，右子树有 n-i 个节点，数量分别是 dp[i-1] 和 dp[n-i]。左右子树的形态可以任意搭配，每个左子树形态都能和每个右子树形态构成一棵完整树，所以这一步贡献是 dp[i-1] * dp[n-i]。把 i=1 到 n 的所有情况加起来，就是 dp[n] = Σ_{i=1}^{n} dp[i-1] * dp[n-i]。
这里乘法怎么来的必须讲透。它不是“左右两种情况相加”，而是“左子树选一种、右子树选一种”的组合。类比一下：你有 3 件上衣和 4 条裤子，能搭配出 12 套衣服，这就是乘法。左右子树互不干扰，可以任意组合，所以用乘法。而换个根节点则是另一批树，是互斥的“或”关系，所以不同根之间用加法。
2.3 手算一遍 n=4，彻底看穿这个递推
光看公式容易晕，动手算一遍就有感觉了。dp[0]=1，dp[1]=1。算 dp[2]：根取 1 时，左子树 0 个节点、右子树 1 个节点，贡献 11=1；根取 2 时，左子树 1 个节点、右子树 0 个节点，贡献 11=1，所以 dp[2]=2。算 dp[3]：根取 1：dp[0]dp[2]=12=2；根取 2：dp[1]*dp[1]=1；根取 3：dp[2]dp[0]=21=2，合计 5。算 dp[4] 同理：
| dp[k] | 计算过程 | 结果 |
|---|---|---|
| dp[0] | 空树约定 | 1 |
| dp[1] | 单节点 | 1 |
| 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 |
| dp[4] | dp[0]*dp[3] + dp[1]*dp[2] + dp[2]*dp[1] + dp[3]*dp[0] = 5+2+2+5 | 14 |
这个序列 1, 1, 2, 5, 14 就是卡特兰数的开头。到这里递推解法已经能通过验证了，O(n²) 的时间，常数也小。但很多题解没有往下讲：为什么偏偏是卡特兰数？这个序列在其他地方见过吗？
3. 卡特兰数：同一个递推，在括号、出栈、二叉树之间流转
3.1 卡特兰数到底是一组什么数字
卡特兰数（Catalan number）是一类自然数序列，从 C0 开始是 1, 1, 2, 5, 14, 42, 132, 429, 1430... 它满足的递推关系是 C0=1，Cn = Σ_{i=0}^{n-1} Ci * C(n-1-i)。我们把 dp[k] 编号和 Cn 对齐一下：dp[0]=C0，dp[1]=C1，dp[2]=C2，dp[3]=C3……你看 dp 的公式：令 dp[k]=Ck，则 dp[n] = Σ_{i=1}^{n} C(i-1) * C(n-i) = Σ_{j=0}^{n-1} Cj * C(n-1-j)，和卡特兰数递推完全一样。
这个结果并不意外，因为卡特兰数本身就是为“划分成两个独立子问题”这类结构而生的。有意思的地方在于，这个递推不是孤例。组合数学里有一整批看起来八竿子打不着的问题，数出来的答案都是这串数字。
3.2 三个经典结构的等价性：二叉树、括号、出栈序列
我先列三个问题，它们的答案全都是卡特兰数：
- n 个节点的二叉树的形态数（不区分节点值，只看形状）；
- n 对括号能组成的合法括号序列数量；
- 1..n 依次入栈，可能的出栈序列数量。
可能有人会问：BST 计数和二叉树形态计数是一回事吗？在本题里是的，因为值 1 到 n 是固定分配的。给定一个二叉树的形状，按中序遍历顺序把 1..n 填进节点，就得到一棵 BST；反过来，把 BST 的节点值抹掉，就是一个二叉树形状。所以 BST 数量和二叉树形态数量恰好一一对应，这也是为什么很多讲卡特兰数的资料会直接用“二叉树形态数”作为例子——同一个数学对象在不同问题里的投射。
为什么这三类结构数量一样？它们满足同一个递推关系，而递推关系唯一决定序列，所以数量必然相等。组合数学里甚至可以构造出两两之间的双射。拿 n=3 来说，5 种合法括号序列是 ((()))、(()())、(())()、()(())、()()()，5 种二叉树形态可以按前序遍历的方式一一对应上去。出栈序列同理：把“入栈”想成左括号、“出栈”想成右括号，任意时刻出栈不能超过入栈次数，正好就是括号匹配的条件。
3.3 通项公式：C(2n,n)/(n+1) 是怎么来的，以及该不该用它
卡特兰数还有一个避开 O(n²) 递推的通项公式：Cn = C(2n, n) / (n+1)。比如 C3 = C(6,3)/4 = 20/4 = 5，C10 = C(20,10)/11 = 16796。
这个公式的来源用生成函数可以解释。设卡特兰数的生成函数 C(x) = Σ_{n≥0} Cn * x^n，由递推关系 Cn = Σ Ci * C(n-1-i) 可以发现它满足 C(x) = 1 + x·C(x)²，解二次方程得到 C(x) = (1 - sqrt(1-4x)) / (2x)，再通过展开比较系数，就得到组合数形式。这段读不懂也没关系，它属于“知道结论、会验证”即可的级别，刷题阶段不需要你现场推导生成函数。
工程上要不要用通项公式？我的建议是分场景。如果你只求本题精确值，n 不超过 19，O(n²) 递推已经足够轻松。但如果你写的是 C++/Java，n 一旦再大些，中间组合数很容易溢出 long，此时反而应该回到递推，或者用大整数类型处理。用公式的前提是你清楚数据范围和溢出边界，盲目套公式的翻车率比递推高得多。
4. 代码实现的完整细节：填表、边界、溢出这三点最容易翻车
4.1 标准的自底向上填表写法
代码本身不长，真正值得看的是细节：
def numTrees(n: int) -> int: dp = [0] * (n + 1) dp[0] = 1 dp[1] = 1 for m in range(2, n + 1): for i in range(1, m + 1): dp[m] += dp[i - 1] * dp[m - i] return dp[n]外层循环 m 从 2 到 n，表示当前要计算的节点总数；内层 i 枚举根节点取值。这里有个关键：内层访问的是 dp[i-1] 和 dp[m-i]，两者都小于 m，而外层的 m 是从 2 递增的，所以 dp 里编号更小的项目都已经算好了，可以放心用。如果你把循环顺序写反，先枚举 i 再枚举 m，那 dp[m-i] 很可能还没算出来，结果就是一堆零在相加，这种 bug 在外层变量名也叫 n、内层也叫 n 的代码里尤其隐蔽。我建议把规模变量用 m 来表示，心里默念“由小到大填表”。
Java/C++ 版本几乎一致，用 long 数组即可：
public int numTrees(int n) { long[] dp = new long[n + 1]; dp[0] = 1; dp[1] = 1; for (int m = 2; m <= n; m++) { for (int i = 1; i <= m; i++) { dp[m] += dp[i - 1] * dp[m - i]; } } return (int) dp[n]; }dp[0]=1 这个约定在代码里是必须的，少了它 dp[2] 会直接算错。它的含义是“空树”也是形态之一，看起来像废话，但在递推里，根节点值取 1 时左子树是空的，这时需要乘上一个“1”而不是“0”，否则整个递推塌掉。
4.2 数据范围与溢出验证：int 是陷阱，long 是底线
这道题给定的 n 上限是 19，我一度觉得 int 就够了，后来算了算才发现这个边界卡得相当紧。卡特兰数成长极快，C19 = 1767263190，刚好处在 int 上限 2147483647 以内；但 C20 = 6564120420，直接越界。所以如果面试官冷不丁把 n 放宽到 20，int 版代码当场就挂。我的习惯是：但凡题目没有明说“结果保证在 int 范围内”，一律用 long，甚至用 Python 的话就完全不用管这档子事。C++ 写 long long，Java 写 long，代价几乎为零，收益是少一次翻车。
顺便说一个自测小技巧：卡特兰数前几项是 1, 1, 2, 5, 14, 42, 132... 你可以把这些数字写死在测试用例里。跑通 dp 逻辑之后，用 n=5 验证输出是不是 42，用 n=10 验证 16796。这比脑补递推过程快得多，我每次写完这类 DP 题都会用“小样本经验值”先撞一遍，没问题再提测。
4.3 记忆化递归版本：什么时候用它
再看递归加记忆化的写法：
from functools import lru_cache def numTrees(n: int) -> int: @lru_cache(None) def dfs(k: int) -> int: if k <= 1: return 1 return sum(dfs(i - 1) * dfs(k - i) for i in range(1, k + 1)) return dfs(n)它和自底向上的 DP 在逻辑上完全等价，好处是思路更贴近递推公式本身，不容易写错循环边界；坏处是有 Python 递归深度限制，n 很大时会报错。对这种小规模问题随便用，但训练时我会建议你两种都写一遍：一遍自顶向下帮助你理解“子问题是什么”，一遍自底向上帮助你建立“填表顺序”的直觉。如果真正要在生产环境里写这类计数逻辑，自底向上版本更可控，也好加单元测试。
5. 面试与实战：识别卡特兰数的三个信号，以及等价题的解题套路
5.1 三个识别信号
把这一节放在最后，因为它是把“会做一道题”变成“会做一类题”的关键。经过前面这一整套分析，我总结出三个信号，只要同时命中，十有八九就是卡特兰数：
- 信号一：问题可以被一个“中心元素”切成左右两半，而且左右两半互相独立。比如二叉树选根、括号序列选某一个外括号对、出栈序列选最后一个出栈的元素；
- 信号二：左右两半的方案数用乘法合并，不同中心元素的方案用加法累加。这就是卷积形式的递推 Σ f(i) * f(n-i)；
- 信号三：n=0 或 1 的答案是 1，n=2 的答案是 2，n=3 的答案是 5。
信号三看起来最不“算法”，但实测非常救命。很多时候公式没推完，你先用这组小值试算，就知道自己方向对不对了。凡是我见过能把卡特兰数往大里讲的题目，几乎都绕不开这三个信号。
5.2 一组等价题：括号生成、出栈序列、矩阵连乘、凸多边形剖分
这里列个表，方便你横向对照：
| 问题 | 枚举的中心元素 | 左右子问题 |
|---|---|---|
| n 对括号的合法排列 | 某一个“最外括号对” | 内部括号 + 外部括号 |
| 1..n 入栈的出栈序列 | 最后一个出栈的元素 | 它之前的元素 + 它之后的元素 |
| n 个节点的二叉树形态 | 根节点 | 左子树 + 右子树 |
| n+1 个矩阵连乘的加括号方式 | 最后一次相乘的位置 | 左段 + 右段 |
| 凸(n+2)边形的三角剖分 | 某一条边对应的三角形顶点 | 左侧子多边形 + 右侧子多边形 |
括号生成那题是典型的“让你构造而不是计数”：它要求把所有合法序列列出来，所以不能只返回数量，得老老实实回溯。但回溯的过程中你会发现，可行序列的个数恰好也是卡特兰数。做这道题时如果先做过本题，你会立刻反应过来：数量我能算出来，构造就是按递推式的顺序生成而已。这两题凑在一起刷，互相验证，理解会深很多。
5.3 面试现场怎么把这题讲出层次
如果你面试遇到这题，别上来就背公式。面试官真正想看的往往不是你能不能写出 dp，而是你理不理解“为什么是这样”。我一般会按照这个顺序讲：
第一步，说题意里最关键的性质：BST 根节点的值把节点集合切成左右两半，而且两半不共享任何值。第二步，写递推：以 i 为根，左子树 i-1 个节点，右子树 n-i 个节点，方案相乘，再对所有 i 求和。第三步，提一句初始化：dp[0]=1 是空树的约定。第四步，如果面试官追问复杂度，就把 O(n²) 时间、O(n) 空间说清楚。第五步，若能自然接一句“这就是卡特兰数，前几项是 1,1,2,5,14”，通常能加分，因为它说明你不仅仅会背题，还能把题目放回组合数学的坐标系里。
有一个误区我见很多人踩过：把“二叉树的形态数”和“二叉树的排列数”混为一谈。比如 n=3 的二叉树形态只有 5 种，但如果你真的给 3 个节点起名为 a、b、c，允许它们任意排列，那会有 3! = 6 种不同的树，那是另一个计数思路，并不是卡特兰数。做题时一定要盯着“形态”两个字，别被绕进去。
最后再分享一个对我个人帮助很大的记忆方法：把卡特兰数的等价模型当成一个整体去记，而不是背公式。我记的是“选一个分割点，左边独立、右边独立、左右相乘、枚举求和”。遇到新题先找分割点，找到了，卡特兰数的边界值和通项公式都是验证工具；找不到，硬记公式基本也套不进去。这个角度让我在矩阵连乘、三角剖分、括号这些题之间来回切换时毫不费力，建议你也试试。
