一，问题描述
给定一个以字符串形式表示的入栈序列，请求出一共有多少种可能的出栈顺序？如何输出所有可能的出栈序列？
比如入栈序列为：1 2 3 ，则出栈序列一共有五种，分别如下：1 2 3、1 3 2、2 1 3、2 3 1、3 2 1
二，问题分析
先介绍几个规律：
①对于出栈序列中的每一个数字，在它后面的、比它小的所有数字，一定是按递减顺序排列的。
比如入栈顺序为：1 2 3 4。
出栈顺序：4 3 2 1是合法的，对于数字 4 而言，比它小的后面的数字是：3 2 1，且这个顺序是递减顺序。同样地，对于数字 3 而言，比它小的后面的数字是： 2 1，且这个顺序是递减的。....
出栈顺序：1 2 3 4 也是合法的，对于数字 1 而言，它后面没有比它更小的数字。同样地，对于数字 2 而言，它后面也没有比它更小的数字。
出栈顺序：3 2 4 1 也是合法的，对于数字 3 而言，它后面比 3 小的数字有： 2 1，这个顺序是递减的；对于数字 2 而言，它后面的比它 小的数字只有 1，也算符合递减顺序；对于数字 4 而言，它后面的比它小的数字也只有1，因此也符合递减顺序。
出栈顺序：3 1 4 2 是不合法的，因为对于数字 3 而言，在3后面的比3小的数字有：1 2，这个顺序是一个递增的顺序(1-->2)。
因此，当给定一个序列时，通过这个规律 可以轻松地判断 哪些序列是合法的，哪些序列是非法的。
②给定一个入栈顺序：1 2 3 .... n，一共有多少种合法的出栈顺序？参考：百度百科卡特兰数
答案是 卡特兰数。即一共有：h(n)=c(2n,n)/(n+1) 种合法的出栈顺序。
待续
卡特兰数是组合数学中的一种数列，它的来历和重要性可以自行百度，我主要说它的特征和编程实现。
前几项是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:
int numTrees(intn){
if(n== 0 || n == 1)return1;
int ret(0);
for(int i(0); i < n; ++i)ret += numTrees(i)*numTrees(n- 1 - i);
return ret;
}//numTrees
};
利用第一个递推式的迭代版本代码，形式上是一致，省去重复计算，比递归的速度快。开辟了vector<int>G(n+ 1)这个数组，存储中间计算结果，本质上是一种动态规划，属于“以土地换和平”的策略。
class Solution {
public:
int numTrees(int n) {
vector<int> G(n + 1);
G[0] = G[1] = 1;
for(int i(2); i <= n; ++i) {
int sum(0);
for(int j(0); j < i; ++j) sum += G[j] * G[i - 1 - j];
G[i]= sum;
}//for i
return G[n];
}//numTrees
};
利用最后那个公式直接求解。
class Solution {
public:
int numTrees(int n) {
if(n == 0 || n == 1)return 1;
long long ret(1);
for(int i(n + 1); i <= n + n; ++i) ret *= i, ret /= i - n;
ret /=n + 1;
return ret;
}//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 {
int val;
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:
int times = 0;
vector<TreeNode*>generateTrees_recur(int left, intright) {
if (left > right)return vector<TreeNode*>{NULL};
vector<TreeNode*>roots;
for (int i(left); i <= right; ++i) {
auto leftRoots = generateTrees_recur(left, i - 1);
auto rightRoots = generateTrees_recur(i + 1, right);
int sizeOfLeft = (int)leftRoots.size();
int sizeOfRight = (int)rightRoots.size();
for (int lch(0); lch < sizeOfLeft; ++lch) {
for (int rch(0); rch < sizeOfRight; ++rch) {
TreeNode*root = new TreeNode(i);
++times;
root->left = leftRoots[lch];
root->right = rightRoots[rch];
roots.push_back(root);
}//for rch
}//for lch
}//for i
return roots;
}//generateTrees_recur
void preOrder(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
void printVec(const vector<int> &vec) {
for (auto num : vec)printf("%d ", num); putchar(10);
return;
}//printVec
void destroyTree(TreeNode *root) {
if (root) {
delete root;
root = NULL;
}//if
return;
}//destroyTree
};
#define CRTDBG_MAP_ALLOC
#include<crtdbg.h>
int main() {
_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
Solution sol;
int n(4);
auto trees = sol.generateTrees(n);
printf("times=%d\n", sol.times);
for (auto tree : trees) {
vector<int>order;
sol.preOrder(tree, order);
sol.destroyTree(tree);
sol.printVec(order);
}//for tree
return 0;
}//main
generateTrees_recur返回的树的个数正好对应一个卡塔兰数。
参考上面的代码，给出一个类似的。
让递归函数generateTrees_recur返回vector<vector<int>>，
然后把对应的vector<int>，用createTree函数，先序建立tree。
得到vector<TreeNode*> trees。也完成了leetcode95题的功能。
我们再把思维在发散一下，vector<int>正好可以应用在别的问题里，比如出栈的顺序。因此这份代码也可以应用在求出栈顺序的那个上面。