卡特蘭數是組合數學中的一種數列，它的來歷和重要性可以自行百度，我主要說它的特征和編程實現。
前幾項是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>正好可以應用在別的問題里，比如出棧的順序。因此這份代碼也可以應用在求出棧順序的那個上面。
新聞熱點
疑難解答
