题解 | #二叉树的个数#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算二叉树个数
# @param n int整型 二叉树结点个数
# @return int整型
#
class Solution:
    def numberOfTree(self , n: int) -> int:
        # write code here
        # 递推公式：fn = fn-1 * （4n-2）/（n+1）
        ans = 1
        # if n == 100000:  #这个数会超时，单独讨论
        #     return 945729344
        for i in range(1, n + 1):
            ans = ans * (4 * i - 2) // (i + 1) #公式
        return int(ans % 1000000007)

        # 有一组结果没通过，超时
        # dp = [0 for _ in range(n + 1)]
        # dp[0] = 1
        # for i in range(1, n + 1):
        #     for j in range(i):
        #         dp[i] += dp[j] * dp[i - 1 - j] #相乘相加
        # return int(dp[n] % 1000000007) #取余