从动态规划到卡特兰数：不同二叉搜索树计数完全解析

1. 从一道题到一类数二叉搜索树与卡特兰数的缘分前阵子在刷题群里看到有人吐槽“不同的二叉搜索树”这道经典动态规划题说看到 $n3$ 要输出5的时候整个人都是懵的——明明感觉组合情况不算多可真去枚举又容易漏。我当时回了一句这题的暴力枚举其实挺有意思但你要是知道卡特兰数后面一堆问题都能串起来。先说这题是干嘛的。给定一个正整数 $n$要求返回由 $1$ 到 $n$ 这 $n$ 个节点能组成多少种结构不同的二叉搜索树。注意是“结构不同”也就是说我们只关心树的形态不关心节点上具体放什么值。因为二叉搜索树有个天然性质中序遍历一定是有序的所以只要形态确定了节点值的填充方式就唯一确定了。换句话说题目等价于问$n$ 个节点能构成多少种不同形态的二叉树。这题适合谁看我觉得有三类人值得花点时间刚开始学动态规划想理解“状态转移方程到底是怎么推出来的”而不是背模板的人学过卡特兰数但只记得公式、不清楚它为什么能用来数二叉树形态的人准备面试的人——这题在不少公司的算法面试里属于“看着简单但能连环追问”的典型考完这道还能顺手考你“怎么构造所有BST”或者“第k个BST是什么”背后的知识是成体系的。我自己当年第一次做这题的时候老老实实用了动态规划后来学组合数学的时候发现卡特兰数可以一行公式直接算但再后来发现“公式党”容易翻车——因为很多变种题没法直接套通项公式反而DP的思维框架能迁移过去。这篇就把两条路线都拆开讲清楚顺便把那些书上不写的推导细节和踩坑点补上。2. 动态规划解法为什么每个节点都要当一次根2.1 状态定义与转移方程的核心逻辑用一个简单例子入手。$n3$ 时节点是 ${1,2,3}$总共有5种BST。你手动枚举会发现可以按根节点分类根为1左子树为空右子树由 ${2,3}$ 组成右子树的形态有2种根为2左子树由 ${1}$ 组成右子树由 ${3}$ 组成左右各1种所以 $1 \times 11$ 种根为3左子树由 ${1,2}$ 组成左子树的形态有2种右子树为空。加起来是 $2125$。这里的关键是当根节点取值为 $i$ 时左子树只能用比 $i$ 小的节点 ${1,\dots,i-1}$ 来构造右子树只能用比 $i$ 大的节点 ${i1,\dots,n}$ 来构造。由于二叉搜索树只要求相对大小关系左子树有 $i-1$ 个节点、右子树有 $n-i$ 个节点它们能形成的形态数量只取决于节点个数不取决于节点的具体值。于是状态 $dp[i]$ 就可以定义为“$i$ 个连续节点能构成的不同BST数量”。转移方程很自然$$ dp[i] \sum_{j1}^{i} dp[j-1] \times dp[i-j] $$其中 $j$ 就是根节点的位置$dp[j-1]$ 是左子树的数量$dp[i-j]$ 是右子树的数量。你会发现这本质上是一个卷积形式的递推每一个 $dp[i]$ 都由前面所有 $dp$ 值的乘积累加得到所以时间复杂度是 $O(n^2)$——准确说是 $\sum_{i1}^{n} i O(n^2)$。空间复杂度是 $O(n)$只需要一个一维数组。2.2 手算 n4 的完整递推过程光看公式容易飘我们实际手算一遍 $dp[4]$。基础值$dp[0]1$空树算一种$dp[1]1$。$dp[2] dp[0] \times dp[1] dp[1] \times dp[0] 112$$dp[3] dp[0] \times dp[2] dp[1] \times dp[1] dp[2] \times dp[0] 2125$$dp[4] dp[0] \times dp[3] dp[1] \times dp[2] dp[2] \times dp[1] dp[3] \times dp[0] 522514$结果就是14。这个数在卡特兰数序列里也很眼熟$C_01, C_11, C_22, C_35, C_414$。所以你用DP算出来的结果本质上就是在算卡特兰数。注意一个细节$dp[0]$ 必须初始化为1不能是0。否则 $dp[1]$ 直接算成0后面全崩。我见过不少同学在这个地方栽跟头因为直觉上会觉得“0个节点的树不存在”但在组合计数里空树也是一种合法结构它代表“某一边没有子树”的情况。2.3 为什么这个DP没有重复计数一个常见的疑问是按根节点分类会不会重复计算同一种树不会。因为每棵BST的根节点是唯一的。给定任意一棵BST它的根节点一定是某个确定的值 $j$左子树和右子树也一定是确定的。当我们固定 $j$ 时左子树和右子树的形态组合就唯一确定了一棵树。不同 $j$ 之间不可能产生同一棵树因为根节点不同同一 $j$ 下不同子树的组合也不同。所以这是一个干净、不重不漏的划分。这也是这道题作为“动态规划入门经典”的原因它的状态设计非常自然转移方程完全来源于对二叉搜索树结构性质的分析不需要任何贪心猜测也不需要状态压缩技巧。2.4 复杂度与边界情况的工程视角在实际写代码的时候$n$ 的范围通常不会很大。比如常见的题目约束是 $n \le 19$此时答案最多是 1767263190刚好卡在32位整数边缘有的版本会要求 $n \le 20$答案变成 6564120420就必须用64位整数long long或语言自带的大整数。这个很容易忽略你要是用C的 int$n20$ 直接溢出WA到怀疑人生。另外有些变种题会要求输出“模 $10^97$ 的结果”这种时候就不能用卡特兰数的通项公式直接算除法取模了——除非你预处理逆元。但用DP递推式的话全程只有加法和乘法没有除法取模非常干净。所以我个人建议即便你熟练掌握了卡特兰数公式遇到取模题也优先用 $O(n^2)$ 的DP代码短、思路直、不怕逆元写错。3. 卡特兰数视角一个公式背后的多重等价定义3.1 递推式、通项公式与生成函数卡特兰数有很多种定义方式它们是完全等价的做题的时候从不同角度切入会有不同便利。第一种是递推式$$ C_01,\quad C_n \sum_{i0}^{n-1} C_i C_{n-1-i} $$这和BST的DP转移完全是一回事只是下标错开一位。BST的 $dp[n]$ 就是卡特兰数 $C_n$。第二种是通项公式$$ C_n \frac{1}{n1}\binom{2n}{n} $$这个公式可以直接用来算 $n19$ 以内的答案O(1) 时间只算一次组合数。不过组合数本身计算需要预处理阶乘或直接乘除$n$ 较大时容易溢出中间结果比如 $\binom{38}{19}$ 是很大的数直接算会爆int需要用 long long 或 Python 的大整数。第三种是生成函数。设 $C(x) \sum_{n\ge 0} C_n x^n$由递推式可得$$ C(x) 1 xC(x)^2 $$解得$$ C(x) \frac{1-\sqrt{1-4x}}{2x} $$生成函数的好处是它能统一处理很多带约束的变种问题比如“左右子树的高度差不超过某值”“节点带权”之类的扩展但二叉搜索树基础题用不太到我也就不展开太多知道有这么个东西就行。3.2 卡特兰数的几个等价组合解释卡特兰数之所以在算法题里高频出现是因为它同时“接管”了好几种计数问题换个包装就不认识它了。有 $n$ 对括号的所有合法括号序列数量是 $C_n$。为什么和BST有关因为BST的中序遍历对应一种括号匹配结构每个节点入栈/出栈一次。$n$ 个元素经过栈操作能得到的不同出栈序列数量是 $C_n$。这和BST形态的对应关系体现在“左右子树划分”和“栈内元素进出”的一致性上。对角线不穿过主对角线的“单调路径”数量是 $C_n$。想象 $n \times n$ 网格里从 $(0,0)$ 走到 $(n,n)$只向右/向上走且任何时候 $x \ge y$不越过对角线路径数就是 $C_n$。这个解释在证明通项公式时非常直观。我自己记卡特兰数的钥匙是括号序列$n3$ 时所有合法括号序列是((()))、(()())、(())()、()(())、()()()正好5个。以后看到任何问题如果穷举小规模结果是 1, 1, 2, 5, 14, 42基本可以往卡特兰数方向猜。3.3 通项公式怎么从递推式推导出来很多人背得住公式但不知道它怎么来的。这里给一个相对简短的推导思路用的是生成函数法能让你对公式有底气得多的信任感。由 $C(x) 1 xC(x)^2$把这个二次方程解出来$$ C(x) \frac{1 \pm \sqrt{1-4x}}{2x} $$因为 $C(0)1$$n0$ 时只有空序列而 $\frac{1\sqrt{1-4x}}{2x}$ 在 $x0$ 处是发散的分子趋于2、分母趋于0所以取负号$$ C(x) \frac{1-\sqrt{1-4x}}{2x} $$然后用广义二项式定理展开 $\sqrt{1-4x} (1-4x)^{1/2}$提取 $x^n$ 项的系数经过几步代数整理就能得到 $C_n \frac{1}{n1}\binom{2n}{n}$。完整推导过程在组合数学教材里都有笔者当年也抄写过两三遍印象最深的是中间会出现 $\binom{2n}{n}-\binom{2n}{n1}$ 这样的差它其实对应“所有路径数减去越界路径数”和网格路径的证明殊途同归。这里不把每一步系数展开写全因为对做题来说你会用通项公式、知道它和递推式等价就足够了。真到需要用生成函数技巧的题再回头啃推导不迟。3.4 实现通项公式的注意事项如果选择直接用通项公式写代码有两个坑。第一$n$ 稍微大一点$\binom{2n}{n}$ 的中间计算会非常大。即使最终结果在64位范围内中间阶乘也可能超出64位。比如 $n15$ 时 $\binom{30}{15}155117520$ 没问题但如果你按“先乘后除”的顺序用 int 计算中途的阶乘值会爆。第二$\frac{1}{n1}\binom{2n}{n}$ 的除法必须在最后做并且要保证整除。因为 $\binom{2n}{n}$ 恰好能被 $n1$ 整除这是卡特兰数为整数的关键性质。如果你用浮点数除法再取整$n$ 稍大就可能因为浮点误差得到错误结果。所以我的建议是如果题目不要求取模且 $n \le 20$用Python直接算组合数最省事用C就老老实实DP只有需要处理 $n$ 很大的取模场景才去学阶乘逆元预处理法。4. 实操过程三种代码实现与本地验证4.1 动态规划实现Cclass Solution { public: int numTrees(int n) { vectorlong long dp(n 1, 0); dp[0] 1; for (int i 1; i n; i) { for (int j 1; j i; j) { dp[i] dp[j - 1] * dp[i - j]; } } return (int)dp[n]; } };这个实现里我用long long做累加因为 $dp[i]$ 中间值可能超过int范围$dp[19] 1767263190$ 正好在int极限边缘$dp[20]$ 就超了。最后强转 int 只是适配题目返回值如果你自己测试 $n19$ 就发现已经溢出。时间复杂度 $O(n^2)$空间 $O(n)$。这个代码没有额外技巧但胜在稳不需要预处理组合数、不需要逆元任何环境下都能跑。4.2 通项公式实现Pythonimport math def num_trees(n: int) - int: return math.comb(2 * n, n) // (n 1)Python的math.comb在3.8可用底层用的是高效算法并且直接返回大整数所以不用担心中间溢出。//做整除也是稳妥的因为卡特兰数必然是整数。如果你偏要自己实现组合数def num_trees(n: int) - int: res 1 for i in range(1, n 1): res res * (n i) // i return res // (n 1)上面的循环利用了一个恒等式$\binom{2n}{n} \prod_{i1}^{n} \frac{ni}{i}$。每次乘完立刻除以 $i$可以保证中间结果是整数避免大数爆炸。这是组合数递推里的经典技巧。4.3 构造所有二叉搜索树扩展实现面试里经常从“数有多少种”跳到“把所有树列出来”。这时候卡特兰数只告诉我们数量但具体的树得用递归构造。思路是枚举根节点 $i$递归构造左子树集合由 $1$ 到 $i-1$ 组成和右子树集合由 $i1$ 到 $n$ 组成然后做笛卡尔积。class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right def generate_trees(n: int): def build(lo, hi): if lo hi: return [None] res [] for i in range(lo, hi 1): left_trees build(lo, i - 1) right_trees build(i 1, hi) for l in left_trees: for r in right_trees: res.append(TreeNode(i, l, r)) return res return build(1, n) if n else []这个递归的时间复杂度是多少总共有 $C_n$ 棵树每棵树要 $O(n)$ 时间构造所以整体是 $O(n \cdot C_n)$。$n15$ 时 $C_{15}$ 是 9694845总操作接近1.5亿已经开始吃力。$n20$ 以上基本不可行所以这题通常约束在 $n \le 8$ 或 $n \le 10$ 左右。4.4 验证与测试样例写完后用几个已知值验证$n1\to1$$n2\to2$$n3\to5$$n4\to14$$n5\to42$。如果结果能对上 1, 1, 2, 5, 14, 42 这个序列基本可以确认实现正确。我习惯额外测一个 $n10$卡特兰数 $C_{10}16796$。这个数不算大但足以排除一些“小规模刚好碰对”的隐患。实测三种方法在这个规模下输出一致DP耗时几乎为0通项公式也几乎为0。5. 常见问题与排查技巧实录5.1 dp[0]0 导致全盘皆错如果你把dp[0]初始化为0计算 $dp[1]$ 时是dp[0]*dp[0] 0之后每个值都错。而且这种错不报错、不越界纯逻辑错误调试时很难发现。排查技巧先用 $n1$ 做单元测试输出必须是1。这个最小用例能挡住一大批初始化错误。5.2 整数溢出int 与 long long 的选择在C里如果n20正确答案是 6564120420超过 int 上限2147483647但题目如果只让你返回 int这就很尴尬——说明题目设计者通常不会让你算到 $n20$。我见过某题库里 $n$ 的上限恰好是 19返回 int 没问题但如果有扩展数据就要用 long long。提示不确定范围时一律用 long long 累加最后再转成题目要求的返回类型。宁可多占几个字节也不想调试溢出问题。5.3 通项公式取模场景下的除法问题如果在模 $10^97$ 环境下用通项公式直接math.comb(2*n, n) // (n1) % MOD是不行的——因为除法在取模世界里没有直接对应必须把除法换成“乘以 $n1$ 的逆元”。具体做法是先求 $n1$ 的模逆元用费马小定理即pow(n1, MOD-2, MOD)然后res comb_mod(2 * n, n) * pow(n 1, MOD - 2, MOD) % MOD这个comb_mod还需要预处理阶乘和阶乘逆元。每次步都对但代码量比DP大多了。所以再次建议取模题直接上DP省心省力还不容易错。5.4 混淆“节点值不同”与“结构不同”有个常见混淆题目说 $n3$ 输出5但有同学非要枚举出6种因为他觉得“根为1左空右{2,3}”和“根为3左{1,2}右空”算不同是没错但他还想把 {2,3} 左右子树排序也区分成两种情况——比如右子树根为2或右子树根为3。这里要注意BST的左右子树结构就是由根节点的位置和递归结构决定的{2,3} 这个集合确实能构成2种不同形态根2右3根3左2我们已经在 $dp[2]2$ 里包含了。如果你又额外在乘的时候考虑顺序就重复计数了。核心原则每棵树由根节点 左子树结构 右子树结构唯一表示不存在“同一组子树但有不同排列”这种说法因为树本身就是有序结构。5.5 递归构造所有树时出现重复有人在generate_trees里会把同一个子树对象l复用到多个根上导致生成后修改一个就影响一片。Python里对象是引用多个树共享同一个TreeNode实例会互相污染。解决方法是每次都新建节点node TreeNode(i, l, r)递归时l和r本身也是新构造的所以没问题。不要做类似l build(lo, i-1)后直接拿来挂多个父节点——因为你在创建每棵树的过程中build返回的列表里的每个元素都是新生成的TreeNode挂在不同的父亲下不会互相影响真正危险的是你在循环体外缓存了同一个TreeNode实例然后反复使用这种错误多出现在手写递归时图省事把某个子树抽出来当作公共变量。5.6 卡特兰数记错前几项这个错误看着低级但真的好多人犯。卡特兰数列是 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862… 有人记成 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862… 其实没错但我见过有人把第5项写成 41 或 52大概是手动枚举时漏了。稳妥的办法是每次用括号序列或网格路径法重新验证前几项尤其 $n3$ 的 5 和 $n4$ 的 14 是高频确认点。6. 一些想提醒你的经验把这道题吃透之后你会发现一个思维钩子只要一个问题里出现“划分成左右两部分且两部分独立计数”这就出现了卡特兰数的影子。比如多边形三角剖分、圆上点连弦不相交、矩阵链乘的加括号方式本质上都是同一个递推结构。我自己刷题时真正从这道题受益的点不是记住了卡特兰数公式而是理解了“以某个元素为根/分割点把问题分解成独立子问题”的套路。这个套路在后续很多树形DP、区间DP里反复出现比如“不同的二叉搜索树 II”要求输出所有树、“表达式加括号优先级”这类题目全都用同一套思路。最后分享一个排查技巧当你用 DP 算出的阶乘级数字和卡特兰数公式的结果对不上时先别急着查公式拿 $n4$ 或 $n5$ 手动画一遍结构看你的递推是不是漏了某个子树为空的情况。 $dp[0]1$ 这个初始化值就是最容易漏的那个“空子树也算一种形态”的抽象表达。能做对这一层组合计数的基础就算是真的打牢了。