lintcode：不同的二叉查找树

卡特兰数
其前几项为 : 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, …

class Solution:
    # @paramn n: An integer
    # @return: An integer
    def numTrees(self, n):
        # write your code here
        if n == 0 or n == 1:
            return 1
        return self.comb(2*n, n)/(n + 1)

    # 阶乘
    def factorial(self, n):
        a = 1
        for i in range(1, n + 1):
            a = a * i
        return a

    # 组合
    def comb(self, downnum, upnum):
        fenzi = self.factorial(downnum)
        fenmu_1 = self.factorial(upnum)
        fenmu_2 = self.factorial(downnum - upnum)
        return fenzi/(fenmu_1 * fenmu_2)