1 引入问题
对于一颗有N个节点的二叉树，可以变化成多少种形态呢？例如：1、3、5、6、9、10可以组成多少种不同的二叉树形态？
2 卡特兰数
百度百科搜“卡特兰数”看了半天没看懂，但是搜了一个网页后看懂了递推思路了：
对于一个规模为n的问题，先找一个元素固定下来，然后将剩下的n-1个元素拆分成两个子问题。卡特兰数一些项：h(0)＝1(规定)，h(1)＝1，h(2)＝2，h(3)＝5，h(4)＝14，h(5)＝42，h(6)＝132，h(7)＝429，h(8)＝1430，h(9)＝4862，h(10)＝16796，h(11)＝58786，h(12)＝208012，h(13)＝742900，h(14)＝2674440，h(15)＝9694845 ····················
关于公式的说明，参考下网友这篇文章《卡特兰数》
3 二叉树形态推理
常规套路，先选一个点当根节点，用f(n)表示n个节点的二叉树不同的形态数，假设左子树有i个节点，右子树有n-i-1个节点，那么根据乘法原理，就有f(i)*f(n-i-1)种方案.把每个点为根的方案数加起来就是答案：f(n) = Σf(i)*f(n-i-1)。
4 其他类似问题
4.1 AB排列问题
有n个A和n个B排成一排，从第1个位置开始到任何位置，B的个数不能超过A的个数，问：这样的排列有多少种？
分析：从公式入手。符合要求的排列数=总的排列数-不符合要求的排列数。因为要在2n个位置中选择n个位置放A，所以总的排列数为C(2n,n).再来看如何求不符合要求的排列数。首先肯定是要找不符合要求的排列有什么特征，一个不符合要求的排列的特征是：存在一个奇数位2*k+1,有k+1个B，k个A，根据这个还不能得到答案。将2*k+2到n*2位上的A,B互换一下，可以发现最后得到的排列一定是有n+1个B，n-1个A的，也就是说一旦一个排列经过这种操作后有n+1个B，那么这个排列就是不合法的，因为变换前的排列和变换后的排列是一一对应的，我们只需要求出变换后的排列有多少种，就能知道变换前的排列有多少种。即C(2n,n+1)种，答案为C(2n,n) - C(2n,n+1)。正好就是卡特兰数。
4.2 乘法括号问题
乘法加括号：对于连乘a1*a2*a3*......*an,加了括号后就可改变它的运算顺序。问：有多少种不同的运算顺序？
分析：常规套路，先选一个乘号当根节点，构造二叉树，乘号左边就是它的左子树，乘号右边就是它的右子树，剩下的就转化为了例1.
4.3 欧拉多边形分隔问题
设有一个凸多边形，可以用n-3条不相交的对角线将n边形分成n-2个互相没有重叠的三角形，例如n=5，有5种方法。
分析：还是要先找一个元素给固定下来，对于边V1Vn,任选一顶点Vk，向V1和Vn连边。将三角形V1VnVk分割出去，剩下两个多边形，一个多边形有顶点{1，2，3，…，k}，所以是k边形；另一个多边形有顶点{k，k+1,…,n}，所以是（n-k+1）边形。这就是类卡特兰数了.最后的答案为f(n) = Σf(k)*f(n-k+1)。
参考《卡特兰数之凸多边形的三角分隔法》