刷题平台上编号 96 的“不同的二叉搜索树”单看标题像是在考树的遍历或者递归构造可真动手做过的朋友应该都有同感这题压根不是树的题它是组合数学的题核心叫做卡特兰数。第一次见到这题的时候我的第一反应也是老老实实把 n 个节点的所有二叉搜索树都构造出来再数一遍写一半就放弃了——n 到 19树形数量早就突破千万级别递归枚举连单测都跑不完。后来想明白一个道理题目不要求你列出每一棵树只要求说出有多少棵那么任何一棵树的内部结构细节都不重要重要的是“怎么从子问题的规模推算出母问题的规模”。这篇文章就把这条思路完整走一遍从递推公式到卡特兰数再到代码里容易踩的边界和溢出问题适合所有刷题遇到这道题的人也适合想搞懂 DP 计数问题底层逻辑的读者。1. 题目到底在问什么先拆穿二叉搜索树的伪装1.1 关键词是“不同”不是“搜索”先看题意给定一个整数 n求恰由 n 个节点组成且节点值从 1 到 n 互不相同的二叉搜索树有多少种。注意两个限定条件二叉搜索树、值从 1 到 n。题目里的“不同”到底不同在哪它指的是树的结构不同也就是左右子树的形态不一样。节点值虽然各不相同但 BST 的规则左小右大会把值的相对顺序固定下来真正能变的只有树的分叉结构。我们验证一下n1只可能是一棵单节点树答案 1。 n2值 1、2。可以以 1 为根右子树放 2也可以以 2 为根左子树放 1。答案 2。 n3值 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} 里选节点右子树只能从 {i1, i2, ..., n} 里选节点。这句话看起来是废话其实它是整道题的分水岭。想通它递推就是水到渠成。因为左子树的节点数量是 i-1右子树的节点数量是 n-i左右两棵子树各自都是一棵独立的二叉搜索树它们的计数分别就是“i-1 个节点的 BST 数量”和“n-i 个节点的 BST 数量”。注意这里用到的只有节点数量节点值具体从多少到多少根本无所谓——{1,2,3} 能构成的 BST 形态和 {6,7,8} 能构成的 BST 形态在数量上完全一样只是把值换个名字。这个“只关数量、不关具体值”的观察是所有子树计数问题的通用钥匙。2. 从暴力枚举到递推公式核心观察是怎么来的2.1 暴力构造为什么必然失败最容易想到的办法递归生成所有满足条件的 BST放到集合里数个数。n 小的时候比如 n4没问题可一旦 n 稍大就崩了。一个 n19 的 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枚举根节点取值 ii 从 1 到 n左子树有 i-1 个节点右子树有 n-i 个节点数量分别是 dp[i-1] 和 dp[n-i]。左右子树的形态可以任意搭配每个左子树形态都能和每个右子树形态构成一棵完整树所以这一步贡献是 dp[i-1] * dp[n-i]。把 i1 到 n 的所有情况加起来就是 dp[n] Σ_{i1}^{n} dp[i-1] * dp[n-i]。这里乘法怎么来的必须讲透。它不是“左右两种情况相加”而是“左子树选一种、右子树选一种”的组合。类比一下你有 3 件上衣和 4 条裤子能搭配出 12 套衣服这就是乘法。左右子树互不干扰可以任意组合所以用乘法。而换个根节点则是另一批树是互斥的“或”关系所以不同根之间用加法。2.3 手算一遍 n4彻底看穿这个递推光看公式容易晕动手算一遍就有感觉了。dp[0]1dp[1]1。算 dp[2]根取 1 时左子树 0 个节点、右子树 1 个节点贡献 111根取 2 时左子树 1 个节点、右子树 0 个节点贡献 111所以 dp[2]2。算 dp[3]根取 1dp[0]dp[2]122根取 2dp[1]*dp[1]1根取 3dp[2]dp[0]212合计 5。算 dp[4] 同理dp[k]计算过程结果dp[0]空树约定1dp[1]单节点1dp[2]dp[0]*dp[1] dp[1]*dp[0] 112dp[3]dp[0]*dp[2] dp[1]*dp[1] dp[2]*dp[0] 2125dp[4]dp[0]*dp[3] dp[1]*dp[2] dp[2]*dp[1] dp[3]*dp[0] 522514这个序列 1, 1, 2, 5, 14 就是卡特兰数的开头。到这里递推解法已经能通过验证了O(n²) 的时间常数也小。但很多题解没有往下讲为什么偏偏是卡特兰数这个序列在其他地方见过吗3. 卡特兰数同一个递推在括号、出栈、二叉树之间流转3.1 卡特兰数到底是一组什么数字卡特兰数Catalan number是一类自然数序列从 C0 开始是 1, 1, 2, 5, 14, 42, 132, 429, 1430... 它满足的递推关系是 C01Cn Σ_{i0}^{n-1} Ci * C(n-1-i)。我们把 dp[k] 编号和 Cn 对齐一下dp[0]C0dp[1]C1dp[2]C2dp[3]C3……你看 dp 的公式令 dp[k]Ck则 dp[n] Σ_{i1}^{n} C(i-1) * C(n-i) Σ_{j0}^{n-1} Cj * C(n-1-j)和卡特兰数递推完全一样。这个结果并不意外因为卡特兰数本身就是为“划分成两个独立子问题”这类结构而生的。有意思的地方在于这个递推不是孤例。组合数学里有一整批看起来八竿子打不着的问题数出来的答案都是这串数字。3.2 三个经典结构的等价性二叉树、括号、出栈序列我先列三个问题它们的答案全都是卡特兰数n 个节点的二叉树的形态数不区分节点值只看形状n 对括号能组成的合法括号序列数量1..n 依次入栈可能的出栈序列数量。可能有人会问BST 计数和二叉树形态计数是一回事吗在本题里是的因为值 1 到 n 是固定分配的。给定一个二叉树的形状按中序遍历顺序把 1..n 填进节点就得到一棵 BST反过来把 BST 的节点值抹掉就是一个二叉树形状。所以 BST 数量和二叉树形态数量恰好一一对应这也是为什么很多讲卡特兰数的资料会直接用“二叉树形态数”作为例子——同一个数学对象在不同问题里的投射。为什么这三类结构数量一样它们满足同一个递推关系而递推关系唯一决定序列所以数量必然相等。组合数学里甚至可以构造出两两之间的双射。拿 n3 来说5 种合法括号序列是 ((()))、(()())、(())()、()(())、()()()5 种二叉树形态可以按前序遍历的方式一一对应上去。出栈序列同理把“入栈”想成左括号、“出栈”想成右括号任意时刻出栈不能超过入栈次数正好就是括号匹配的条件。3.3 通项公式C(2n,n)/(n1) 是怎么来的以及该不该用它卡特兰数还有一个避开 O(n²) 递推的通项公式Cn C(2n, n) / (n1)。比如 C3 C(6,3)/4 20/4 5C10 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 不超过 19O(n²) 递推已经足够轻松。但如果你写的是 C/Javan 一旦再大些中间组合数很容易溢出 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 放宽到 20int 版代码当场就挂。我的习惯是但凡题目没有明说“结果保证在 int 范围内”一律用 long甚至用 Python 的话就完全不用管这档子事。C 写 long longJava 写 long代价几乎为零收益是少一次翻车。顺便说一个自测小技巧卡特兰数前几项是 1, 1, 2, 5, 14, 42, 132... 你可以把这些数字写死在测试用例里。跑通 dp 逻辑之后用 n5 验证输出是不是 42用 n10 验证 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)信号三n0 或 1 的答案是 1n2 的答案是 2n3 的答案是 5。信号三看起来最不“算法”但实测非常救命。很多时候公式没推完你先用这组小值试算就知道自己方向对不对了。凡是我见过能把卡特兰数往大里讲的题目几乎都绕不开这三个信号。5.2 一组等价题括号生成、出栈序列、矩阵连乘、凸多边形剖分这里列个表方便你横向对照问题枚举的中心元素左右子问题n 对括号的合法排列某一个“最外括号对”内部括号 外部括号1..n 入栈的出栈序列最后一个出栈的元素它之前的元素 它之后的元素n 个节点的二叉树形态根节点左子树 右子树n1 个矩阵连乘的加括号方式最后一次相乘的位置左段 右段凸(n2)边形的三角剖分某一条边对应的三角形顶点左侧子多边形 右侧子多边形括号生成那题是典型的“让你构造而不是计数”它要求把所有合法序列列出来所以不能只返回数量得老老实实回溯。但回溯的过程中你会发现可行序列的个数恰好也是卡特兰数。做这道题时如果先做过本题你会立刻反应过来数量我能算出来构造就是按递推式的顺序生成而已。这两题凑在一起刷互相验证理解会深很多。5.3 面试现场怎么把这题讲出层次如果你面试遇到这题别上来就背公式。面试官真正想看的往往不是你能不能写出 dp而是你理不理解“为什么是这样”。我一般会按照这个顺序讲第一步说题意里最关键的性质BST 根节点的值把节点集合切成左右两半而且两半不共享任何值。第二步写递推以 i 为根左子树 i-1 个节点右子树 n-i 个节点方案相乘再对所有 i 求和。第三步提一句初始化dp[0]1 是空树的约定。第四步如果面试官追问复杂度就把 O(n²) 时间、O(n) 空间说清楚。第五步若能自然接一句“这就是卡特兰数前几项是 1,1,2,5,14”通常能加分因为它说明你不仅仅会背题还能把题目放回组合数学的坐标系里。有一个误区我见很多人踩过把“二叉树的形态数”和“二叉树的排列数”混为一谈。比如 n3 的二叉树形态只有 5 种但如果你真的给 3 个节点起名为 a、b、c允许它们任意排列那会有 3! 6 种不同的树那是另一个计数思路并不是卡特兰数。做题时一定要盯着“形态”两个字别被绕进去。最后再分享一个对我个人帮助很大的记忆方法把卡特兰数的等价模型当成一个整体去记而不是背公式。我记的是“选一个分割点左边独立、右边独立、左右相乘、枚举求和”。遇到新题先找分割点找到了卡特兰数的边界值和通项公式都是验证工具找不到硬记公式基本也套不进去。这个角度让我在矩阵连乘、三角剖分、括号这些题之间来回切换时毫不费力建议你也试试。