对一棵树或者子树进行先序或者中序遍历时入栈顺序相同。
都是根节点、左子树、右子树，（注意是入栈）
先序访问后入栈，中序出栈后访问，
则先序序列就是入栈顺序，中序序列就是出栈顺序。
卡特兰数应用之出栈次序：
问题：一个栈的进栈序列为1,2,3，…，n。有多少个不同的出栈序列？
分析：设f(n) = 序列个数为n的出栈序列种数。设最后出栈的元素为k。即在k进栈之前，元素1,2,…，k-1已经出栈，出栈序列数为f(k-1)。在k进栈后，元素k+1,k+2,…，n已经进栈后全部出栈。所以元素k+1,k+2,…,n出栈序列种数为f(n-k)。由于比k小和比k大的值入栈出栈情况是相互独立的，此处可用乘法原则，f(n-k)*f(k-1)种，求和便是Catalan递归式。
解决：f(n) = f(n-k)*f(k-1),其中k=1,2,3,…,n 所以f(n) = h(n)= C(2n,n)/(n+1) = c(2n,n)-c(2n,n+1)（n=0,1,2,3,…,n）
因篇幅问题不能全部显示，请点此查看更多更全内容