卡特兰数是组合数学中的一种数列，它的来历和重要性可以自行百度，我主要说它的特征和编程实现。
前几项是1, 1, 2, 5, 14, 42, 132……，
如果令h(0)=h(1)=1,那么h(n)=h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)*h(0) (n>=2)。
常用递推公式h(n)=C(2n,n)/(n+1) =(2n)!/n!/(n+1)!,(n=0,1,2,...)，还有很多变体。
利用程序来求解这些数值自然简单。
比如利用第一个递推式的递归版本代码
classSolution{
public:
intnumTrees(intn){
if(n== 0 || n == 1)return1;
intret(0);
for(inti(0); i < n; ++i)ret += numTrees(i)*numTrees(n- 1 - i);
returnret;
}//numTrees
};
利用第一个递推式的迭代版本代码，形式上是一致，省去重复计算，比递归的速度快。开辟了vector<int>G(n+ 1)这个数组，存储中间计算结果，本质上是一种动态规划，属于“以土地换和平”的策略。
class Solution {
public:
intnumTrees(int n) {
vector<int>G(n + 1);
G[0] =G[1] = 1;
for(inti(2); i <= n; ++i) {
intsum(0);
for(intj(0); j < i; ++j) sum += G[j] * G[i - 1 - j];
G[i]= sum;
}//fori
returnG[n];
}//numTrees
};
利用最后那个公式直接求解。
class Solution {
public:
intnumTrees(int n) {
if(n == 0 || n == 1)return 1;
longlongret(1);
for(inti(n + 1); i <= n + n; ++i) ret *= i, ret /= i - n;
ret /=n + 1;
returnret;
}//numTrees
};
以上都是直接求卡特兰数列的某一项值。比较简单。
进一步了解可知，该数列应用在很多实际问题中。比如栈的出入顺序，BST的种类。
下面以搜索二叉树的建立为例给出代码，对于给定一个序列，建立BST，序列中元素的顺序会影响树的形状。
比如{1,2}，能建立起1为根，2为右孩子的BST。而{2,1}则建立起2为根，1为左孩子的BST。
该代码对应leetcode 95题，核心部分为generateTrees_recur函数，递归出口是left>right，返回空子树（即NULL）。
For(i)循环中，先得到leftRoots和rightRoots，分别是左半部分序列得到的子树和右半部分序列得到的子树，后面for(lch,rch)循环来交叉刚才得到的那些子树。
对于每一个交叉，产生一个以i为根的新的子树。
#include<stdio.h>
#include<vector>
using std::vector;
struct TreeNode {
intval;
TreeNode*left = NULL;
TreeNode*right = NULL;
TreeNode(intval_ = -1) :val(val_) {}
~TreeNode(){
if(left) {delete left; left = NULL; }
if(right) {delete right; right = NULL; }
}//~Node
};
class Solution {
public:
vector<TreeNode*>generateTrees(int n) {
if(n == 0)return vector<TreeNode*>{};
returngenerateTrees_recur(1, n);
}//generateTrees
public:
inttimes = 0;
vector<TreeNode*>generateTrees_recur(int left,intright) {
if(left > right)return vector<TreeNode*>{NULL};
vector<TreeNode*>roots;
for(inti(left); i <= right; ++i) {
autoleftRoots = generateTrees_recur(left, i - 1);
autorightRoots = generateTrees_recur(i + 1, right);
intsizeOfLeft = (int)leftRoots.size();
intsizeOfRight = (int)rightRoots.size();
for(intlch(0); lch < sizeOfLeft; ++lch) {
for(intrch(0); rch < sizeOfRight; ++rch) {
TreeNode*root = new TreeNode(i);
++times;
root->left= leftRoots[lch];
root->right= rightRoots[rch];
roots.push_back(root);
}//forrch
}//forlch
}//fori
returnroots;
}//generateTrees_recur
voidPReOrder(TreeNode *root, vector<int>&order) {
if(root == NULL) {
order.push_back(-1);
return;
}//if
order.push_back(root->val);
preOrder(root->left,order);
preOrder(root->right,order);
return;
}//preOrder
voidprintVec(const vector<int>&vec) {
for(autonum : vec)printf("%d ", num);putchar(10);
return;
}//printVec
voiddestroyTree(TreeNode *root) {
if(root) {
deleteroot;
root= NULL;
}//if
return;
}//destroyTree
};
#define CRTDBG_MAP_ALLOC
#include<crtdbg.h>
int main() {
_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF| _CRTDBG_LEAK_CHECK_DF);
Solutionsol;
intn(4);
autotrees = sol.generateTrees(n);
printf("times=%d/n", sol.times);
for(autotree : trees) {
vector<int>order;
sol.preOrder(tree,order);
sol.destroyTree(tree);
sol.printVec(order);
}//fortree
return0;
}//main
generateTrees_recur返回的树的个数正好对应一个卡塔兰数。
参考上面的代码，给出一个类似的。
让递归函数generateTrees_recur返回vector<vector<int>>，
然后把对应的vector<int>，用createTree函数，先序建立tree。
得到vector<TreeNode*> trees。也完成了leetcode95题的功能。
我们再把思维在发散一下，vector<int>正好可以应用在别的问题里，比如出栈的顺序。因此这份代码也可以应用在求出栈顺序的那个上面。
新闻热点
疑难解答
