先序序列为a、b、c、d的不同二叉树的个数是多少（卡特兰数）

除了逻辑清晰的挨个画出来之外，还有一种方法需要大家牢记！

因为前序序列和中序序列可以唯一地确定一棵二叉树，并且题目已经给出了先序序列，所以我们只需要知道由该先序序列可以确定多少个中序序列即可，确定多少个中序序列就是可以确定多少棵二叉树！

那么，问题来了，由一个先序序列如何确定有多少个中序序列呢？这就有两个“公式”需要大家去牢记了！

1、先序序列和中序序列的关系为：以先序序列入栈，则出栈序列必为中序序列。

 2、一个入栈顺序可以确定的出栈顺序为 C(2n,n) / (n+1)（卡特兰数）。

 所以答案就清楚了，如果以abcd的顺序入栈，将有14种出栈顺序，也就是可以确定14个中序序列，即可以确定14个不同的二叉树。