卡特兰数在LeetCode刷题中的5种经典应用场景（附Python代码）
卡特兰数在LeetCode刷题中的5种经典应用场景（附Python代码）
卡特兰数（Catalan Numbers）是组合数学中一个既优美又实用的数列，它在算法问题中扮演着重要角色。对于准备技术面试的开发者来说，掌握卡特兰数的应用场景能快速解决一类特定问题。本文将聚焦LeetCode高频题型，通过5个经典场景展示如何识别卡特兰数特征并实现高效解题。
1. 括号生成问题
LeetCode第22题「括号生成」是卡特兰数的典型应用。要求生成所有有效的n对括号组合，其总数正是第n个卡特兰数。
问题特征识别：
- 需要生成所有合法排列而非计数时，通常需要回溯法
- 仅需计数时，可直接套用卡特兰数公式
- 合法条件：任意前缀中左括号数≥右括号数
Python实现模板：
def generateParenthesis(n): def backtrack(s, left, right): if len(s) == 2*n: res.append(s) return if left < n: backtrack(s+'(', left+1, right) if right < left: backtrack(s+')', left, right+1) res = [] backtrack("", 0, 0) return res # 计数版（卡特兰数公式） def catalan(n): from math import comb return comb(2*n, n) // (n + 1)复杂度对比：
| 方法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 回溯法 | O(4^n/√n) | O(n) |
| 公式法 | O(1) | O(1) |
提示：面试中若只需计数，直接给出卡特兰数结果能显著提升解题效率
2. 二叉树形态计数
LeetCode第96题「不同的二叉搜索树」要求计算由n个节点组成的BST数量，这正是卡特兰数的定义。
问题转化技巧：
- 选定根节点后，左右子树节点数之和为n-1
- 总方案数=Σ(左子树方案×右子树方案)
- 递推式与卡特兰数定义完全一致
动态规划解法：
def numTrees(n): dp = [0]*(n+1) dp[0] = dp[1] = 1 for i in range(2, n+1): for j in range(i): dp[i] += dp[j] * dp[i-j-1] return dp[n] # 数学优化版 def numTrees_math(n): from math import comb return comb(2*n, n) // (n + 1)典型变式题目：
- LeetCode 95：生成所有BST（需要实际构建树）
- LeetCode 894：所有可能的满二叉树
3. 栈排序问题
栈操作相关的计数问题往往隐藏着卡特兰数。例如「合法的出栈顺序总数」就是经典场景。
LeetCode关联题目：
- 验证栈序列（验证合法性）
- 面试题03.05. 栈排序（排序方案数）
特征识别模式：
- 操作序列包含等量的push/pop
- 任意前缀中push次数 ≥ pop次数
- 这与括号问题的限制条件同构
Python模拟解法：
def validateStackSequences(pushed, popped): stack = [] i = 0 for num in pushed: stack.append(num) while stack and stack[-1] == popped[i]: stack.pop() i += 1 return not stack # 计数公式 def stackPermutations(n): return catalan(n)4. 不相交弦问题
在圆周上标记2n个点，用n条不相交的弦连接这些点，求方案总数。这是卡特兰数的几何解释。
LeetCode变形题：
- 不相交的握手（会员题）
- 多边形三角剖分问题
解题思路拆解：
- 固定一个点作为弦的端点
- 将圆分成两个部分，避免弦交叉
- 递推公式：f(n) = Σf(i)*f(n-i-1)
Python实现：
def chordCount(n): 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-j-1] return dp[n]5. 路径不越界问题
在n×n网格中从(0,0)到(n,n)不越过对角线的路径数，对应第n个卡特兰数。
LeetCode代表题目：
- 不同路径（基础版）
- 不同路径 II（带障碍物）
- 不同路径 III（进阶版）
卡特兰数适用条件：
- 网格必须是n×n正方形
- 路径不允许越过主对角线
- 每步只能向右或向上移动
路径计数实现：
def uniquePaths(n): from math import comb return comb(2*n, n) - comb(2*n, n-1) # 动态规划版 def uniquePathsDP(n): dp = [[1]*(n+1) for _ in range(n+1)] for i in range(1, n+1): for j in range(i+1, n+1): dp[i][j] = dp[i-1][j] + dp[i][j-1] return dp[n][n]性能对比表：
| 方法 | n=5 | n=10 | n=20 |
|---|---|---|---|
| 组合公式 | 0.01ms | 0.01ms | 0.01ms |
| 动态规划 | 0.05ms | 0.21ms | 3.4ms |
实战技巧与优化策略
识别卡特兰数问题的关键在于发现递归子结构。当问题满足以下特征时，应考虑卡特兰数解法：
- 分治特性：问题可分解为相似的子问题
- 乘法原理：整体方案数为各子问题方案数的乘积
- 加法原理：需要汇总所有可能的分割方式
记忆化实现模板：
from functools import lru_cache @lru_cache(maxsize=None) def catalan(n): if n <= 1: return 1 res = 0 for i in range(n): res += catalan(i) * catalan(n-1-i) return res预处理卡特兰数表（适合多次查询）：
def precompute_catalan(max_n): catalan = [1]*(max_n+1) for i in range(2, max_n+1): catalan[i] = catalan[i-1]*(4*i-2)//(i+1) return catalan在算法竞赛或面试中，对卡特兰数问题的处理可分为三个层次：
- 初级：识别问题模式，直接套用公式
- 中级：实现动态规划解法，理解递推关系
- 高级：改造问题使其符合卡特兰数模型