面试题：N个节点的二叉树，有多少种形态（二叉树的形状）

分析思路： 

（1）先考虑只有一个节点的情形，设此时的形态有f(1)种，那么很明显f(1)=1

（2）如果有两个节点呢？我们很自然想到，应该在f(1)的基础上考虑递推关系。那么，如果固定一个节点后，左右子树的分布情况为1=1+0=0+1，故有f(2) = f(1) + f(1)

（3）如果有三个节点，我们需要考虑固定两个节点的情况么？当然不，因为当节点数量大于等于2时，无论你如何固定，其形态必然有多种！我们考虑固定一个节点，即根节点。好的，按照这个思路，还剩2个节点，那么左右子树的分布情况为2=2+0=1+1=0+2。 所以有3个节点时，递归形式为f(3)=f(2) + f(1)*f(1) + f(2)。注意这里的乘法，因为左右子树一起组成整棵树，根据排列组合里面的乘法原理即可得出

（4）那么有n个节点呢？我们固定一个节点，那么左右子树的分布情况为n-1=n-1 + 0 = n-2 + 1 = … = 1 + n-2 = 0 + n-1。此时递归表达式为f(n) = f(n-1) + f(n-2)f(1) + f(n-3)f(2) + … + f(1)f(n-2) + f(n-1)

接下来，我们定义没有节点的情况，此时也只有一种情况，即f(0)=1 
那么则有: 

f(0)=1

f(1)=1 

f(2)=f(1)f(0)+f(0)f(1) 

f(3)=f(2)f(0)+f(1)f(1)+f(0)f(2) 

。。。。。。

f(n)=f(n-1)f(0)+f(n-2)f(1)+……….+f(1)f(n-2)+f(0)f(n-1) 

该数列称为卡特兰数（Catalan数），该递推关系的解为： 

即含n个节点的二叉树有f(n)种形态。

 

卡塔兰数（Catalan）是组合数学中一个常在各种计数问题中出现的数列。以比利时的数学家欧仁·查理·卡塔兰（1814–1894）命名。历史上，清代数学家明安图(1692年－1763年)在其《割圜密率捷法》最早用到“卡塔兰数”，远远早于卡塔兰。有中国学者建议将此数命名为“明安图数”或“明安图-卡塔兰数”。

卡塔兰数的一般公式为 C(2n,n)/(n+1)

令h(0)=1,h(1)=1，卡塔兰数满足递归式：

h(n)= h(0)*h(n-1) + h(1)*h(n-2) + ... + h(n-1)h(0) (其中n>=2)，这是n阶递推关系;

还可以化简为1阶递推关系，如：h(n)=(4n-2)/(n+1)*h(n-1)(n>1) h(0)=1

该递推关系的解为：h(n)=C(2n,n)/(n+1)=P(2n,n)/(n+1)!=(2n)!/(n!*(n+1)!) (n=1,2,3,...)

卡塔兰数列的前几项为(sequence A 0 0 0 1 0 8 in OEIS) [注： n = 0, 1, 2, 3, … n]

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, …

 

Catalan数的简单代码实现 (python) 

class Solution:
    def numTrees(self, n: int) -> int:
        #初始化一个数组，并将首个元素初始化为1
        s=[0]*(n+1)
        s[0]=1
 
        #开始循环遍历
        for i in range(1,n+1):
            #为节约内存，首先算出i-1的值
            b=i-1
 
            #为节约内存，只遍历一半，并将这个结果乘以2即可
            for j in range(i//2):
                s[i]+=s[j]*s[b-j]
            s[i]*=2
 
            #当i为奇数时，还要将s[i//2]的值加上
            if i%2==1:
                s[i]+=s[i//2]**2
 
        #返回数组最后一个元素
        return s[-1]

 

Catalan数解决的问题

(1) 矩阵链乘： P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？ 

(2) 一个栈(无穷大)的进栈序列为1,2,3,..n, 有多少个不同的出栈序列? 

(3) 有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？(将持5元者到达视作将5元入栈，持10元者到达视作使栈中某5元出栈) 

(4) 将一个凸多边形区域分成三角形区域的方法数? 

(5) 在圆上选择2n个点，将这些点成对连接起来，使得所得到的n条线段不相交的方法数。 

(6) 一位大城市的律师在她住所以北n个街区和以东n个街区处工作，每天她走2n个街区去上班。如果她从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？

 

 

参考推荐：

卡特兰(Catalan)数入门详解

各种基本算法实现小结（三）——树与二叉树

LeetCode 543. 二叉树的直径 (任意两结点最长距离)

树与二叉树的深度优先与广度优先算法（递归与非递归）

【leetcode】Maximum Depth of BinaryTree

面试最常用的10大算法

八大排序算法图文讲解