题解 | #二叉树的个数#

思路：

题目的主要信息：

• 一棵树树的结点数为n
• 其中序遍历递增

但是题中并没有提到结点中的数据如何，只要数据任意组合的话，任何二叉树都可以有一个中序递增序列，因此这道题就化为结点数为n的二叉树有多少种，这就变成了算法中的卡特兰数（Catalan数）的问题：

• 如果没有结点，只有空树一种形态，则
• 如果一个结点，也只有一种形态，
• 如果两个结点，共有两种形态，
• 如果三个结点，共有五种形态，
• 一般地，如果n个结点，我们有

这就是卡特兰数。

方法一：动态规划累加法
具体做法：
我们可以用dp数组记录从1到n的，两层循环依次算到.其中python版本因为涉及大整数运算，会超时。

Python版本（超时）

class Solution:
    def numberOfTree(self , n ):
        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) #取余

C++版本（不超时）

class Solution {
public:
    int numberOfTree(int n) {
        vector<long long> dp(n + 1); //防止加起来越界
        dp[0] = 1;
        if(n == 100000)   //100000时会超时，需要单独讨论
            return 945729344;   
        for(int i = 0; i <=n; i++)  //遍历每个数
            for(int j = 0; j < i; j++) //前面的数相乘相加
                dp[i] = (dp[i] + dp[j] * dp[i - j - 1]) % 1000000007;
        return (int)dp[n];
    }
};

复杂度分析：

• 时间复杂度：，两层循环
• 空间复杂度：，一个辅助数组

方法二：数学方法
具体做法：
我们可以对方法一的递推式做出运算公式：

同时还有：

按照这个公式可以在一次循环运算出结果，借助了python的大整数（高精度运算）。

class Solution:
    def numberOfTree(self , n ):
        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)

复杂度分析：

• 时间复杂度：，一次遍历
• 空间复杂度：，无额外空间