链接：https://leetcode.cn/circle/article/lWYCzv/
一、引言
卡特兰数（Catalan number）是组合数学中一个常出现在各种计数问题中的数列。
数列的前几项为：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862，...
本文将会选取几个经典的卡特兰问题，难度先易后难，带领读者逐个击破解决，最后给出相关的解题模板。
二、经典问题
2.1 进出栈序列
这是一道最经典的入门级卡特兰数题目，如果能把这题看懂，相信后面的题目也能迎刃而解。
题目描述：
n 个元素进栈序列为：1，2，3，4，...，n，则有多少种出栈序列
思路：
我们将进栈表示为 +1，出栈表示为 -1，则 1 3 2 的出栈序列可以表示为：+1 -1 +1 +1 -1 -1。
根据栈本身的特点，每次出栈的时候，必定之前有元素入栈，即对于每个 -1 前面都有一个 +1 相对应。因此，出栈序列的所有前缀和必然大于等于 0，并且 +1 的数量等于 -1 的数量，除非这是一个错误的序列。
接下来让我们观察一下 n = 3 的一种出栈序列：+1 -1 -1 +1 -1 +1。序列前三项和小于 0，显然这是个非法的序列。
此时如果将第一个前缀和小于 0 的前缀取反，即前三项元素都进行取反，就会得到：-1 +1 +1 +1 -1 +1。此时有 3 + 1 个 +1 以及 3 - 1 个 -1。
因为这个小于 0 的前缀和必然是 -1，且 -1 比 +1 多一个，通过取反之后，-1 反而比 +1 少一个，则 +1 变为 n + 1 个，且 -1 变为 n - 1 个。
通过进一步推广，对于 n 元素的每种非法出栈序列，都会对应一个含有 n + 1 个 +1 以及 n - 1 个 -1 的序列。
如何证明这两种序列是一一对应的呢❓❓❓
假设非法的序列为 A，其对应的序列为 B。每个 A 只有一个**"第一个前缀和小于 0 的前缀"**，所以每个 A 只能产生一个 B。而每个 B 想要还原到 A，就需要找到 "第一个前缀和大于 0 的前缀"，显然 B 也只能产生一个 A。
每个 B 都有 n + 1 个 +1 以及 n - 1 个 -1，因此 B 的数量为 
，相当于在长度为 2n 的序列中找到 n + 1 个位置存放 +1。
相应的，非法序列 A 的数量也就等于。
出栈序列的总数量共有
，因此，合法的出栈序列的数量为
。此时我们就得到了卡特兰数的通项！至于具体如何计算结果将会在后面进行介绍。
2.2 括号序列
题目描述：
n 对括号，则有多少种 “括号匹配” 的括号序列。
思路：
左括号看成 +1，右括号看成 -1，那么就和上题的进出栈一样，共有
种序列！
2.3 二叉树
题目描述：
n + 1 个叶子节点能够构成多少种形状不同的（国际）满二叉树。
国际满二叉树的定义：如果一棵二叉树的结点要么是叶子结点，要么它有两个子结点，这样的树就是满二叉树。
这和我们常见的满二叉树的定义不太一样！
思路：
使用深度优先搜索这个满二叉树，向左扩展时标记为 +1，向右扩展时标记为 -1。
由于每个非叶子节点都有两个左右子节点，所有它必然会先向左扩展，再向右扩展。总体下来，左右扩展将会形成匹配，即变成进出栈的题型。n + 1 个叶子结点会有 2n 次扩展，构成
种形状不同的满二叉树。
（国际）满二叉树满足非叶子节点数
m+1 = n（叶子节点数），总共会有2n条边，所以会有2n次扩展 证明：设有m个非叶子节点,p为总节点数,q为边数 满足：m + n = p; p = q + 1； 2*m = q; 消去p,q可得
2.4 电影购票
题目描述：
电影票一张 50 硬币，且售票厅没有硬币。m 个人各自持有 50 硬币，n 个人各自持有 100 硬币。则有多少种排队方式，可以让每个人都买到电影票。
思路：
持有 50 硬币的人每次购票时不需要找零，并且可以帮助后面持有 100 硬币的人找零；而对于持有 100 硬币的人每次购票时需要找零，但 100 硬币对后面的找零没有任何作用。
因此，相当于每个持有 100 硬币的人都需要和一个持有 50 硬币的人进行匹配。我们将持有 50 硬币的标记为 +1，持有 100 硬币的标记为 -1，此时又回到了进出栈问题。
不同的是，m 并一定等于 n，且排队序列是一种排列，需要考虑先后顺序，例如各自持有 50 硬币的甲和乙的前后关系会造成两种不同的排队序列。所以，将会有
第二项为什么是
，其实很简单，我们每次把 第一个前缀小于 0 的前缀取反后，会造成
+1多了一个而-1少了一个。这里+1有m个，-1有n个，取反后+1变成m + 1个，-1变成n - 1个，总和不变。
三、解题模板
最后我们需要来计算一下卡特兰数的通项
💥💥💥卡特兰数满足以下递推式：
因此，我们可以通过递推来得到第 n 个卡特兰数。
需要注意的是，由于卡特兰数增长速度较快，当
n等于17时，卡特兰数将会超过int最大值，造成溢出！
那如果 +1 的数量不等于 -1 的数量呢，如前面提到的电影购票问题。此时
，不是卡特兰数的通项，也就不能够继续使用原有的递推性质。
那就直接推导：
一般而言，为了降低难度，题目会要求我们计算排列数量，所以
总结如下：
