从一道二叉树面试题理解卡塔兰数：DP、格点路径与反射原理
从 n 个节点能组成多少种二叉树出发，逐步推导动态规划、卡塔兰递推、格点路径、反射原理、合法括号与多种等价模型。面向算法面试与 ACM 竞赛。
有这样一道常见的算法题：给定非负整数 n，求恰好包含 n 个节点的不同二叉树形状数量。
两棵树形状相同，当且仅当它们的根节点、左子树形状和右子树形状分别相同。左右子树交换后通常视为不同形状。空树也计为一种形状，因此 n = 0 时答案为 1。
前几项是：
n = 0 -> 1
n = 1 -> 1
n = 2 -> 2
n = 3 -> 5
n = 4 -> 14
n = 5 -> 42也就是数列 1, 1, 2, 5, 14, 42, 132, 429, ...。这就是卡塔兰数（Catalan Number）。
闭式公式很短：
C_n = 1 / (n + 1) * binom(2n, n)不过只背这个公式很容易忘。下面从二叉树 DP 出发，依次把二叉树、格点路径、合法括号、栈、前缀和与反射原理连起来。
从二叉树 DP 开始
定义 dp[n] 表示恰好使用 n 个节点时，不同二叉树形状的数量。
空树为什么算一种
边界条件是：
dp[0] = 1只有一个节点时，左右子树都是空树：
o
/ \
∅ ∅如果令 dp[0] = 0，那么 dp[1] = dp[0] * dp[0] = 0，显然不对。组合数学和动态规划经常把“什么都不选”或“空结构”视作一种合法方案，原因就在这里。
固定根节点，枚举左右子树
一棵含有 n 个节点的树先拿出一个节点作为根，剩余 n - 1 个节点分给左右子树。
如果左子树使用 i 个节点，右子树就使用 n - 1 - i 个节点。左、右子树可以独立选择，固定 i 时共有：
dp[i] * dp[n - 1 - i]种组合。枚举 i = 0, 1, ..., n - 1，得到：
dp[n] = sum(dp[i] * dp[n - 1 - i], i = 0..n-1)展开就是：
dp[n] = dp[0]dp[n-1] + dp[1]dp[n-2] + ... + dp[n-1]dp[0]这已经是完整的动态规划解法。
手算 n = 3
从 dp[0] = 1 开始：
dp[1] = dp[0]dp[0]
= 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]
= 1 * 2 + 1 * 1 + 2 * 1
= 5n = 2 对应的两棵树是：
o o
\ /
o oPython 实现
def count_binary_trees(n: int) -> int:
dp = [0] * (n + 1)
dp[0] = 1
for nodes in range(1, n + 1):
for left_nodes in range(nodes):
right_nodes = nodes - 1 - left_nodes
dp[nodes] += dp[left_nodes] * dp[right_nodes]
return dp[n]ACM 输入输出模式：
n = int(input())
dp = [0] * (n + 1)
dp[0] = 1
for nodes in range(1, n + 1):
for left_nodes in range(nodes):
right_nodes = nodes - 1 - left_nodes
dp[nodes] += dp[left_nodes] * dp[right_nodes]
print(dp[n])时间复杂度为 O(n^2)，空间复杂度为 O(n)。
识别卡塔兰递推
刚才得到的递推：
dp[0] = 1
dp[n] = sum(dp[i] * dp[n - 1 - i], i = 0..n-1)正是卡塔兰数最经典的递推定义：
C_0 = 1
C_n = sum(C_i * C_(n - 1 - i), i = 0..n-1)所以 dp[n] = C_n。前几项如下：
| n | C_n |
|---|---|
| 0 | 1 |
| 1 | 1 |
| 2 | 2 |
| 3 | 5 |
| 4 | 14 |
| 5 | 42 |
| 6 | 132 |
| 7 | 429 |
| 8 | 1430 |
| 9 | 4862 |
| 10 | 16796 |
为什么二叉树问题会产生这个数列？可以换到一个看起来完全不同的格点路径问题。
格点路径模型
考虑一个 n * n 的方格。蚂蚁从 (0, 0) 出发走到 (n, n)，每一步只能向右走一步 R 或向上走一步 U，并且整条路径不能走到直线 y = x 的上方：
y <= x这个问题的答案同样是 C_n。
没有限制时的路径数量
从 (0, 0) 到 (n, n) 必须走 n 次 R 和 n 次 U，一共 2n 步。在 2n 个位置中选择 n 个位置放 R，路径总数是：
binom(2n, n)例如 n = 3 时，所有路径共有 binom(6, 3) = 20 条。
加入 y <= x 的限制以后，任意前缀都必须满足：
#R >= #URRRUUU 和 RURURU 都合法；URRRUU 不合法，因为第一步就到达 (0, 1)，越过了对角线。
二维 DP
定义 dp[x][y] 表示从 (0, 0) 走到 (x, y)，并且始终满足 y <= x 的路径数量。
到达 (x, y) 的最后一步只可能来自左边 (x - 1, y) 或下方 (x, y - 1)，因此：
dp[x][y] = dp[x - 1][y] + dp[x][y - 1]只计算 y <= x 的区域；对于 y > x，直接令 dp[x][y] = 0。
n = 3 时的 DP 表为：
x
0 1 2 3
y = 3 X X X 5
y = 2 X X 2 5
y = 1 X 1 2 3
y = 0 1 1 1 1X 表示 y > x 的非法区域。对角线上的值依次是 1, 1, 2, 5, ...，仍然是卡塔兰数。
def catalan_grid(n: int) -> int:
dp = [[0] * (n + 1) for _ in range(n + 1)]
dp[0][0] = 1
for x in range(n + 1):
for y in range(n + 1):
if y > x or (x == 0 and y == 0):
continue
if x > 0:
dp[x][y] += dp[x - 1][y]
if y > 0:
dp[x][y] += dp[x][y - 1]
return dp[n][n]时间和空间复杂度都是 O(n^2)。实际只计算三角区域，状态数为 (n + 1)(n + 2) / 2，数量级不变。
二叉树与格点路径之间的双射
二维 DP 和二叉树 DP 得到同一个数并非巧合。两种结构之间可以建立双射：每一棵二叉树唯一对应一条合法格点路径，每一条合法格点路径也能唯一还原成一棵二叉树。
用前序遍历编码二叉树
对二叉树进行前序遍历，同时记录空孩子：
真实节点 -> 1
空节点 -> 0只有一个节点时：
o
/ \
∅ ∅
前序编码：1 0 0两个节点时，下面两棵树分别编码为 1 1 0 0 0 和 1 0 1 0 0：
o o
/ \
o o不同树形会得到不同编码。
为什么有 n + 1 个空孩子
每个真实节点提供两个孩子位置，一共有 2n 个位置。一棵有 n 个节点的树内部有 n - 1 条真实父子边，所以空位置数量是：
2n - (n - 1) = n + 1完整前序编码中有 n 个 1、n + 1 个 0，总长度为 2n + 1。
合法编码一定以 0 结尾。删除最后一个 0 后，剩下 n 个 1 和 n 个 0。再定义：
1 -> R
0 -> U就得到一条从 (0, 0) 到 (n, n) 的格点路径。
为什么路径不会越过 y = x
从前往后解析二叉树编码。最开始有一个根位置等待填入，所以 slots = 1。
- 遇到真实节点
1：占掉一个位置，同时产生两个孩子位置，净变化为+1。 - 遇到空节点
0：占掉一个位置，不再产生孩子，净变化为-1。
完整解析结束前，slots 不可能变成 0 或负数，否则树已经提前结束。因此，删除最后一个 0 后的任意前缀都满足：
#1 >= #0映射成 R 和 U 后就是 #R >= #U。坐标中 x = #R、y = #U，所以整条路径始终满足 y <= x。
一个完整例子
考虑下面这棵树：
A
/ \
B C
/ \ / \
∅ ∅ ∅ ∅前序编码为：
A B ∅ ∅ C ∅ ∅
1 1 0 0 1 0 0删除最后一个 0，再映射成路径：
1 1 0 0 1 0
R R U U R U对应坐标序列：
(0,0) -> (1,0) -> (2,0) -> (2,1)
-> (2,2) -> (3,2) -> (3,3)整个过程中始终满足 y <= x。
这套转换是可逆的。路径可以唯一变回 0/1 编码，补上最后一个固定的 0 后，又能按照前序规则唯一恢复二叉树：
二叉树
<-> 前序 0/1 编码
<-> n 个 R 与 n 个 U
<-> 不越过 y = x 的格点路径因此，n 个节点的二叉树与 n 阶合法格点路径构成双射。
用反射原理得到闭式
二维 DP 能计算答案，反射原理可以直接推导闭式。
所有从 (0, 0) 到 (n, n) 的路径共有 binom(2n, n) 条。合法路径数等于总路径数减去越过 y = x 的非法路径数。
第一次越界点
任意非法路径都存在第一次进入 y > x 的位置。每次只走一格，所以第一次越界时恰好满足 y = x + 1。把这个点记作 P。
例如路径 RUURRU 走完前缀 RUU 时到达 (1, 2)，这是第一次满足 y = x + 1。
只把起点到 P 的路径前缀关于直线 y = x + 1 反射。P 在反射轴上，位置不变；起点 (0, 0) 会变成 (-1, 1)。于是，一条从 (0, 0) 到 (n, n) 的非法路径，被映射为一条从 (-1, 1) 到 (n, n) 的普通路径。
为什么这是一一对应
反过来，任取一条从 (-1, 1) 到 (n, n) 的路径，定义 d = y - x。
起点处 d = 2，终点处 d = 0。每一步只会让 d 增加或减少 1，所以路径一定经过 d = 1，也就是直线 y = x + 1。找到第一次到达该直线的位置 P，再次反射从 (-1, 1) 到 P 的前缀，就恢复了原来的非法路径。
映射与逆映射都是唯一的，因此非法路径与从 (-1, 1) 到 (n, n) 的普通路径构成双射。
计算非法路径数量
从 (-1, 1) 到 (n, n)，横向需要 n + 1 步，纵向需要 n - 1 步，总计 2n 步。因此非法路径数量为：
binom(2n, n - 1)合法路径数量是：
C_n = binom(2n, n) - binom(2n, n - 1)利用：
binom(2n, n - 1) = n / (n + 1) * binom(2n, n)最终得到卡塔兰数闭式：
C_n = 1 / (n + 1) * binom(2n, n)
= (2n)! / (n! * (n + 1)!)从格点路径重新得到递推
格点路径也能推出与二叉树相同的递推。
一条合法路径的第一步一定是 R，否则会立刻进入 y > x。假设它第一次重新回到对角线的位置是 (k + 1, k + 1)，整条路径可以唯一拆成：
R + A + U + B其中 A 是规模为 k 的合法卡塔兰结构，B 是规模为 n - 1 - k 的合法卡塔兰结构。固定 k 时有 C_k * C_(n - 1 - k) 种组合。枚举 k = 0, 1, ..., n - 1：
C_n = sum(C_k * C_(n - 1 - k), k = 0..n-1)二叉树通过枚举左子树大小完成递归分解；格点路径通过枚举第一次回到对角线的位置完成分解。两者使用的是同一种结构。
合法括号与非负前缀和
把格点路径映射为：
R -> (
U -> )路径限制 #R >= #U 就变成任意前缀中左括号数量不少于右括号数量，这正是合法括号序列的定义。因此，n 对合法括号序列的数量也是 C_n。
n = 3 时共有 5 种：
((()))
(()())
(())()
()(())
()()()还可以把 R 记为 +1、U 记为 -1。合法路径要求前缀和 S_k >= 0，最终 S_(2n) = 0。
例如：
R R U R U U
+1 +1 -1 +1 -1 -1
前缀和：1 2 1 2 1 0所有前缀和都非负。若序列以 U 开头，第一步的前缀和就是 -1，立即非法。
括号、栈、格点路径和二叉树可以放进同一个“资源”模型：
| 模型 | +1：产生资源 | -1：消耗资源 | 合法性条件 |
|---|---|---|---|
| 括号 | ( 创建待闭合括号 | ) 闭合一个括号 | 右括号不能过多 |
| 栈 | push 放入元素 | pop 取出元素 | 不能从空栈弹出 |
| 格点路径 | R | U | y <= x |
| 二叉树编码 | 真实节点净增加一个待填位置 | 空节点消耗一个待填位置 | 待填位置不能提前耗尽 |
统一条件就是：
任意前缀：S_k >= 0
最终状态：S_(2n) = 0为什么不同二叉搜索树也是卡塔兰数
LeetCode 96“不同的二叉搜索树”是另一个经典卡塔兰问题。给定 1, 2, ..., n，选择 k 作为根时，比 k 小的 k - 1 个元素只能进入左子树，比 k 大的 n - k 个元素只能进入右子树。因此：
dp[n] = sum(dp[k - 1] * dp[n - k], k = 1..n)换一下变量就是同一个卡塔兰递推。
更直接地看，一旦 BST 的树形确定，将 1, ..., n 按中序遍历从小到大填入，节点值也唯一确定。因此，n 个节点的二叉树形状数量等于 n 个不同键能构成的 BST 数量，答案都是 C_n。
常见卡塔兰问题
下面这些问题的答案通常是 C_n：
n个节点的不同二叉树形状；n个不同键能构造的 BST；n对合法括号；- 从
(0, 0)到(n, n)且不越过y = x的格点路径； 2n个人两两握手，圆内连线互不相交的方案；- 凸
n + 2边形的三角剖分； 1, 2, ..., n依次入栈时的合法出栈序列。
栈模型中，push 对应 +1，pop 对应 -1。任意前缀中 pop 次数不能超过 push 次数，否则就是从空栈继续弹出。
ACM 中如何识别卡塔兰结构
判断一道题是否与卡塔兰数有关，应该看结构，而不是只看前几项数值。
递归拆成左右两部分
一个规模为 n 的对象拆成规模为 i 和 n - 1 - i 的两个独立同类对象，出现类似下面的递推：
f(n) = sum(f(i) * f(n - 1 - i), i = 0..n-1)
f(0) = 1这是很强的卡塔兰信号。
任意前缀不能“欠债”
例如：
- 左括号数量不少于右括号数量；
push次数不少于pop次数；R的数量不少于U；- 有同样多的
+1和-1，且前缀和不能小于0。
非交叉结构
非交叉括号、非交叉弦和多边形三角剖分等递归结构，也经常产生卡塔兰数。
三种计算方法
实际比赛中，应根据 n 的范围和模数选择算法。
O(n^2) 动态规划
这种写法最接近定义，不需要组合数学：
def catalan_dp(n: int) -> int:
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
for j in range(i):
dp[i] += dp[j] * dp[i - 1 - j]
return dp[n]时间复杂度为 O(n^2)，空间复杂度为 O(n)，适合 n 不大、需要从定义推导的场景。
组合数公式
Python 支持任意精度整数，可以直接使用 math.comb：
from math import comb
def catalan(n: int) -> int:
return comb(2 * n, n) // (n + 1)相邻项递推
相邻卡塔兰数满足：
C_n = C_(n - 1) * (4n - 2) / (n + 1)因此可以用 O(n) 次递推计算：
def catalan(n: int) -> int:
c = 1
for i in range(1, n + 1):
c = c * (4 * i - 2) // (i + 1)
return c模意义下的卡塔兰数
ACM 题目经常要求对 1_000_000_007 取模。若 MOD 是质数，并且满足这份简单阶乘实现所需的 2n < MOD，可以用费马小定理计算逆元：
MOD = 1_000_000_007
def catalan(n: int) -> int:
fact = [1] * (2 * n + 1)
for i in range(1, 2 * n + 1):
fact[i] = fact[i - 1] * i % MOD
def inv(x: int) -> int:
return pow(x, MOD - 2, MOD)
middle = (
fact[2 * n]
* inv(fact[n])
% MOD
* inv(fact[n])
% MOD
)
return middle * inv(n + 1) % MOD模意义下不能用整数除法 x // y 代替除法，而要乘以 y 的模逆元。如果模数不是质数、分母与模数不互质，或者数据范围越过了简单阶乘法的适用条件，就需要根据题目进一步考虑素因子分解、Lucas 定理、扩展欧几里得、CRT 或质因数指数。
更一般的投票问题
卡塔兰数是 Ballot Problem（投票问题、Bertrand’s Ballot Theorem）的特殊情况。
更一般地，序列中有 a 个 R 和 b 个 U，并要求整个过程中始终满足 #R >= #U。当 a = b = n 时，就回到卡塔兰路径。
竞赛中遇到“A 始终不能落后于 B”一类限制时，可以尝试把它转换成格点路径或前缀和，再考虑反射原理。
面试时如何回答
如果面试官直接问“n 个节点有多少种二叉树”，可以先给出完整推导：
- 设
dp[i]表示i个节点能组成的二叉树数量。 - 固定根节点后，剩余
i - 1个节点分配给左右子树。 - 左子树有
j个节点时，右子树有i - 1 - j个节点，方案数为dp[j] * dp[i - 1 - j]。 - 枚举所有
j，并设置dp[0] = 1。
dp[i] = sum(dp[j] * dp[i - 1 - j], j = 0..i-1)这套 DP 的时间复杂度是 O(n^2)，空间复杂度是 O(n)。进一步识别出卡塔兰递推后，再给出闭式：
C_n = 1 / (n + 1) * binom(2n, n)这样的回答同时说明了状态定义、转移来源、边界条件与数学结构，比只说“答案是卡塔兰数”更完整。
卡塔兰数的增长速度
中央二项式系数满足：
binom(2n, n) ~ 4^n / sqrt(pi * n)代入闭式可得：
C_n ~ 4^n / (sqrt(pi) * n^(3/2))所以卡塔兰数虽然比 4^n 稍慢，仍然是指数级增长。这也解释了为什么数列从 1, 1, 2, 5, 14, 42 很快增长到 429, 1430, 4862, 16796。
总结
从二叉树出发，我们先得到递推：
dp[n] = sum(dp[i] * dp[n - 1 - i], i = 0..n-1)格点路径的二维 DP 给出另一种计算方式：
dp[x][y] = dp[x - 1][y] + dp[x][y - 1], y <= x反射原理则把合法路径计数化成：
C_n = binom(2n, n) - binom(2n, n - 1)
= 1 / (n + 1) * binom(2n, n)二叉树、合法格点路径、合法括号和非负前缀和看似不同，都对应同一种卡塔兰结构。识别卡塔兰数时，重点看两类信号：
f(n) = sum(f(i) * f(n - 1 - i), i = 0..n-1)以及：
任意前缀 S_k >= 0，最终 S_(2n) = 0以后在二叉树、括号、栈、格点路径或非交叉结构中再次遇到这些特征，就可以从卡塔兰数的角度建模。