从一道二叉树面试题理解卡塔兰数：DP、格点路径与反射原理

有这样一道常见的算法题：给定非负整数 $n$，求恰好包含 $n$ 个节点的不同二叉树形状数量。

两棵树形状相同，当且仅当它们的根节点、左子树形状和右子树形状分别相同。左右子树交换后通常视为不同形状。空树也计为一种形状，因此 $n=0$ 时答案为 $1$。

前几项是：

$$\begin{aligned} n=0 &\Rightarrow 1, \\ n=1 &\Rightarrow 1, \\ n=2 &\Rightarrow 2, \\ n=3 &\Rightarrow 5, \\ n=4 &\Rightarrow 14, \\ n=5 &\Rightarrow 42. \end{aligned}$$

也就是数列 $1,1,2,5,14,42,132,429,\ldots$。这就是卡塔兰数（Catalan Number）。

闭式公式很短：

$$C_n=\frac{1}{n+1}\binom{2n}{n}.$$

不过只背这个公式很容易忘。下面从二叉树 DP 出发，依次把二叉树、格点路径、合法括号、栈、前缀和与反射原理连起来。

从二叉树 DP 开始

定义 $\mathrm{dp}[n]$ 表示恰好使用 $n$ 个节点时，不同二叉树形状的数量。

空树为什么算一种

边界条件是：

$$\mathrm{dp}[0]=1.$$

只有一个节点时，左右子树都是空树：

    o
   / \
  ∅   ∅

如果令 $\mathrm{dp}[0]=0$，那么 $\mathrm{dp}[1]=\mathrm{dp}[0]\cdot\mathrm{dp}[0]=0$，显然不对。组合数学和动态规划经常把“什么都不选”或“空结构”视作一种合法方案，原因就在这里。

固定根节点，枚举左右子树

一棵含有 $n$ 个节点的树先拿出一个节点作为根，剩余 $n-1$ 个节点分给左右子树。

如果左子树使用 $i$ 个节点，右子树就使用 $n-1-i$ 个节点。左、右子树可以独立选择，固定 $i$ 时共有：

$$\mathrm{dp}[i]\cdot\mathrm{dp}[n-1-i]$$

种组合。枚举 $i=0,1,\ldots,n-1$，得到：

$$\mathrm{dp}[n] =\sum_{i=0}^{n-1}\mathrm{dp}[i]\,\mathrm{dp}[n-1-i].$$

展开就是：

$$\mathrm{dp}[n] =\mathrm{dp}[0]\mathrm{dp}[n-1] +\mathrm{dp}[1]\mathrm{dp}[n-2] +\cdots +\mathrm{dp}[n-1]\mathrm{dp}[0].$$

这已经是完整的动态规划解法。

手算 $n=3$

从 $\mathrm{dp}[0]=1$ 开始：

$$\begin{aligned} \mathrm{dp}[1] &=\mathrm{dp}[0]\mathrm{dp}[0] =1, \\[4pt] \mathrm{dp}[2] &=\mathrm{dp}[0]\mathrm{dp}[1]+\mathrm{dp}[1]\mathrm{dp}[0] \\ &=1+1=2, \\[4pt] \mathrm{dp}[3] &=\mathrm{dp}[0]\mathrm{dp}[2]+\mathrm{dp}[1]\mathrm{dp}[1]+\mathrm{dp}[2]\mathrm{dp}[0] \\ &=1\cdot2+1\cdot1+2\cdot1=5. \end{aligned}$$

$n=2$ 对应的两棵树是：

    o          o
     \        /
      o      o

Python 实现

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)$。

识别卡塔兰递推

刚才得到的递推：

$$\mathrm{dp}[0]=1, \qquad \mathrm{dp}[n]=\sum_{i=0}^{n-1}\mathrm{dp}[i]\,\mathrm{dp}[n-1-i].$$

正是卡塔兰数最经典的递推定义：

$$C_0=1, \qquad C_n=\sum_{i=0}^{n-1}C_iC_{n-1-i}.$$

所以 $\mathrm{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\times n$ 的方格。蚂蚁从 $(0,0)$ 出发走到 $(n,n)$，每一步只能向右走一步 $R$ 或向上走一步 $U$，并且整条路径不能走到直线 $y=x$ 的上方：

$$y\le 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\le x$ 的限制以后，任意前缀都必须满足：

$$\#R\ge \#U.$$

RRRUUU 和 RURURU 都合法；URRRUU 不合法，因为第一步就到达 $(0,1)$，越过了对角线。

二维 DP

定义 $\mathrm{dp}[x][y]$ 表示从 $(0,0)$ 走到 $(x,y)$，并且始终满足 $y\le x$ 的路径数量。

到达 $(x,y)$ 的最后一步只可能来自左边 $(x-1,y)$ 或下方 $(x,y-1)$，因此：

$$\mathrm{dp}[x][y] =\mathrm{dp}[x-1][y]+\mathrm{dp}[x][y-1].$$

只计算 $y\le x$ 的区域；对于 $y>x$，直接令 $\mathrm{dp}[x][y]=0$。

$n=3$ 时，合法区域会按照依赖顺序逐格累加：

n 3 4 5

↻ → ▶

Loading chart...

Step 1 / 10 dp[0][0] = 1

图中的 $\times$ 表示 $y>x$ 的非法区域。对角线上的值依次是 $1,1,2,5,\ldots$，仍然是卡塔兰数。

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)$。实际只计算三角区域，状态数为

$$\frac{(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\mapsto R, \qquad 0\mapsto U.$$

就得到一条从 $(0,0)$ 到 $(n,n)$ 的格点路径。

为什么路径不会越过 $y=x$

从前往后解析二叉树编码。最开始有一个根位置等待填入，所以 $\mathrm{slots}=1$。

• 遇到真实节点 $1$：占掉一个位置，同时产生两个孩子位置，净变化为 $+1$。
• 遇到空节点 $0$：占掉一个位置，不再产生孩子，净变化为 $-1$。

完整解析结束前，$\mathrm{slots}$ 不可能变成 $0$ 或负数，否则树已经提前结束。因此，删除最后一个 $0$ 后的任意前缀都满足：

$$\#1\ge \#0.$$

映射成 $R$ 和 $U$ 后就是 $\#R\ge\#U$。坐标中 $x=\#R$、$y=\#U$，所以整条路径始终满足 $y\le 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)\to(1,0)\to(2,0)\to(2,1) \to(2,2)\to(3,2)\to(3,3).$$

整个过程中始终满足 $y\le x$。

这套转换是可逆的。路径可以唯一变回 0/1 编码，补上最后一个固定的 0 后，又能按照前序规则唯一恢复二叉树：

$$\text{binary tree} \longleftrightarrow \text{preorder }0/1\text{ encoding} \longleftrightarrow n\text{ }R\text{ steps and }n\text{ }U\text{ steps} \longleftrightarrow \text{a lattice path below }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)$ 的普通路径。

RUURRU Reflect path

Loading chart...

Axis: y = x + 1 Invalid path RUURRU; first crossing P = (1, 2).

为什么这是一一对应

反过来，任取一条从 $(-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} =\frac{n}{n+1}\binom{2n}{n}.$$

最终得到卡塔兰数闭式：

$$C_n =\frac{1}{n+1}\binom{2n}{n} =\frac{(2n)!}{n!(n+1)!}.$$

从格点路径重新得到递推

格点路径也能推出与二叉树相同的递推。

一条合法路径的第一步一定是 $R$，否则会立刻进入 $y>x$。假设它第一次重新回到对角线的位置是 $(k+1,k+1)$，整条路径可以唯一拆成：

$$R+A+U+B.$$

其中 $A$ 是规模为 $k$ 的合法卡塔兰结构，$B$ 是规模为 $n-1-k$ 的合法卡塔兰结构。固定 $k$ 时有 $C_kC_{n-1-k}$ 种组合。枚举 $k=0,1,\ldots,n-1$：

$$C_n=\sum_{k=0}^{n-1}C_kC_{n-1-k}.$$

二叉树通过枚举左子树大小完成递归分解；格点路径通过枚举第一次回到对角线的位置完成分解。两者使用的是同一种结构。

合法括号与非负前缀和

把格点路径映射为：

$$R\mapsto (, \qquad U\mapsto ).$$

路径限制 $\#R\ge\#U$ 就变成任意前缀中左括号数量不少于右括号数量，这正是合法括号序列的定义。因此，$n$ 对合法括号序列的数量也是 $C_n$。

$n=3$ 时共有 $5$ 种：

((()))
(()())
(())()
()(())
()()()

还可以把 $R$ 记为 $+1$、$U$ 记为 $-1$。合法路径要求前缀和 $S_k\ge0$，最终 $S_{2n}=0$。

例如：

$$\begin{array}{c|cccccc} \text{step} & R & R & U & R & U & U \\ \Delta S & +1 & +1 & -1 & +1 & -1 & -1 \\ S_k & 1 & 2 & 1 & 2 & 1 & 0 \end{array}$$

所有前缀和都非负。若序列以 $U$ 开头，第一步的前缀和就是 $-1$，立即非法。

括号、栈、格点路径和二叉树可以放进同一个“资源”模型：

模型	$+1$：产生资源	$-1$：消耗资源	合法性条件
括号	( 创建待闭合括号	) 闭合一个括号	右括号不能过多
栈	push 放入元素	pop 取出元素	不能从空栈弹出
格点路径	$R$	$U$	$y\le x$
二叉树编码	真实节点净增加一个待填位置	空节点消耗一个待填位置	待填位置不能提前耗尽

统一条件就是：

$$S_k\ge0\quad(1\le k\le2n), \qquad S_{2n}=0.$$

为什么不同二叉搜索树也是卡塔兰数

LeetCode 96“不同的二叉搜索树”是另一个经典卡塔兰问题。给定 $1,2,\ldots,n$，选择 $k$ 作为根时，比 $k$ 小的 $k-1$ 个元素只能进入左子树，比 $k$ 大的 $n-k$ 个元素只能进入右子树。因此：

$$\mathrm{dp}[n] =\sum_{k=1}^{n}\mathrm{dp}[k-1]\,\mathrm{dp}[n-k].$$

换一下变量就是同一个卡塔兰递推。

更直接地看，一旦 BST 的树形确定，将 $1,\ldots,n$ 按中序遍历从小到大填入，节点值也唯一确定。因此，$n$ 个节点的二叉树形状数量等于 $n$ 个不同键能构成的 BST 数量，答案都是 $C_n$。

常见卡塔兰问题

下面这些问题的答案通常是 $C_n$：

1. $n$ 个节点的不同二叉树形状；
2. $n$ 个不同键能构造的 BST；
3. $n$ 对合法括号；
4. 从 $(0,0)$ 到 $(n,n)$ 且不越过 $y=x$ 的格点路径；
5. $2n$ 个人两两握手，圆内连线互不相交的方案；
6. 凸 $n+2$ 边形的三角剖分；
7. $1,2,\ldots,n$ 依次入栈时的合法出栈序列。

栈模型中，push 对应 $+1$，pop 对应 $-1$。任意前缀中 pop 次数不能超过 push 次数，否则就是从空栈继续弹出。

ACM 中如何识别卡塔兰结构

判断一道题是否与卡塔兰数有关，应该看结构，而不是只看前几项数值。

递归拆成左右两部分

一个规模为 $n$ 的对象拆成规模为 $i$ 和 $n-1-i$ 的两个独立同类对象，出现类似下面的递推：

$$f(0)=1, \qquad f(n)=\sum_{i=0}^{n-1}f(i)f(n-1-i).$$

这是很强的卡塔兰信号。

任意前缀不能“欠债”

例如：

• 左括号数量不少于右括号数量；
• 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}\frac{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<\mathrm{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\ge\#U$。当 $a=b=n$ 时，就回到卡塔兰路径。

竞赛中遇到“A 始终不能落后于 B”一类限制时，可以尝试把它转换成格点路径或前缀和，再考虑反射原理。

面试时如何回答

如果面试官直接问“$n$ 个节点有多少种二叉树”，可以先给出完整推导：

1. 设 $\mathrm{dp}[i]$ 表示 $i$ 个节点能组成的二叉树数量。
2. 固定根节点后，剩余 $i-1$ 个节点分配给左右子树。
3. 左子树有 $j$ 个节点时，右子树有 $i-1-j$ 个节点，方案数为 $\mathrm{dp}[j]\mathrm{dp}[i-1-j]$。
4. 枚举所有 $j$，并设置 $\mathrm{dp}[0]=1$。

$$\mathrm{dp}[i] =\sum_{j=0}^{i-1}\mathrm{dp}[j]\,\mathrm{dp}[i-1-j].$$

这套 DP 的时间复杂度是 $O(n^2)$，空间复杂度是 $O(n)$。进一步识别出卡塔兰递推后，再给出闭式：

$$C_n=\frac{1}{n+1}\binom{2n}{n}.$$

这样的回答同时说明了状态定义、转移来源、边界条件与数学结构，比只说“答案是卡塔兰数”更完整。

卡塔兰数的增长速度

中央二项式系数满足：

$$\binom{2n}{n}\sim\frac{4^n}{\sqrt{\pi n}}.$$

代入闭式可得：

$$C_n\sim\frac{4^n}{\sqrt{\pi}\,n^{3/2}}.$$

所以卡塔兰数虽然比 $4^n$ 稍慢，仍然是指数级增长。这也解释了为什么数列从 $1,1,2,5,14,42$ 很快增长到 $429,1430,4862,16796$。

总结

从二叉树出发，我们先得到递推：

$$\mathrm{dp}[n] =\sum_{i=0}^{n-1}\mathrm{dp}[i]\,\mathrm{dp}[n-1-i].$$

格点路径的二维 DP 给出另一种计算方式：

$$\mathrm{dp}[x][y] =\mathrm{dp}[x-1][y]+\mathrm{dp}[x][y-1], \qquad y\le x.$$

反射原理则把合法路径计数化成：

$$C_n =\binom{2n}{n}-\binom{2n}{n-1} =\frac{1}{n+1}\binom{2n}{n}.$$

二叉树、合法格点路径、合法括号和非负前缀和看似不同，都对应同一种卡塔兰结构。识别卡塔兰数时，重点看两类信号：

$$f(n)=\sum_{i=0}^{n-1}f(i)f(n-1-i).$$

以及：

$$S_k\ge0\quad(1\le k\le2n), \qquad S_{2n}=0.$$

以后在二叉树、括号、栈、格点路径或非交叉结构中再次遇到这些特征，就可以从卡塔兰数的角度建模。