题目描述（中等难度）

和一样，只不过这道题不需要输出所有的树，只需要输出所有可能的二分查找树的数量。所以完全按照 95 题思路写，大家可以先到 95 题看一看。

解法一递归

下边是 95 题的分析。

对于这道题，我们会更简单些，只需要返回树的数量即可。求当前根的数量，只需要左子树的数量乘上右子树。

受到的启发，我们甚至可以改写的更简单些。因为 95 题要把每颗树返回，所有传的参数是 start 和 end。这里的话，我们只关心数量，所以不需要具体的范围，而是传树的节点的数量即可。


    if (n == 0) {
        return 0;
    }
    return getAns(n);
}
private int getAns(int n) { 
    int ans = 0;
    //此时没有数字或者只有一个数字,返回 1
    if (n==0 ||n==1) { 
        return 1;
    } 
    //尝试每个数字作为根节点
    for (int i = 1; i <= n; i++) {
        //得到所有可能的左子树
        int leftTreesNum = getAns(i-1);
        //得到所有可能的右子树
        int rightTreesNum  = getAns(n-i);
        //左子树右子树两两组合
        ans+=leftTreesNum * rightTreesNum;
    }
    return ans;
}

解法二动态规划

直接利用95题解法三的思路，讲解比较长就不贴过来了，可以过去看一下。

或者直接从这里的解法一的思路考虑，因为递归是从顶层往下走，压栈压栈压栈，到了长度是 0 或者是 1 就出栈出栈出栈。我们可以利用动态规划的思想，直接从底部往上走。求出长度是 0，长度是 1，长度是 2….长度是 n 的解。用一个数组 dp 把这些结果全部保存起来。

public int numTrees(int n) {
    int[] dp = new int[n + 1];
    dp[0] = 1;
    if (n == 0) {
        return 0;
    }
    // 长度为 1 到 n
    for (int len = 1; len <= n; len++) {
        // 将不同的数字作为根节点，只需要考虑到 len
        for (int root = 1; root <= len; root++) {
            int left = root - 1; // 左子树的长度
            int right = len - root; // 右子树的长度
    }
    return dp[n];
}

参考还有优化的空间。

利用对称性，可以使得循环减少一些。

n 是偶数的时候 1 2 | 3 4 ，for 循环中我们以每个数字为根求出每个的解。我们其实可以只求一半，根据对称性我们可以知道 1 和 4，2 和 3 求出的解分别是相等的。
n 是奇数的时候

1 2 | 3 | 4 5，和偶数同理，只求一半，此外最中间的 3 的解也要加上。

解法三公式法

参考这里-timesO(1)space>)。其实利用的是卡塔兰数列，这是第二次遇到了，之前是第，生成合法的括号序列。

这道题，为什么和卡塔兰数列联系起来呢？

看一下卡塔兰树数列的定义：

令h ( 0 ) = 1，catalan 数满足递推式：

h ( n ) = h ( 0 ) * h ( n - 1 ) + h ( 1 ) * h ( n - 2 ) + … + h ( n - 1 ) * h ( 0 ) ( n >=1 )

例如：h ( 2 ) = h ( 0 ) * h ( 1 ) + h ( 1 ) * h ( 0 ) = 1 * 1 + 1 * 1 = 2

h ( 3 ) = h ( 0 ) * h ( 2 ) + h ( 1 ) * h ( 1 ) + h ( 2 ) * h ( 0 ) = 1 * 2 + 1 * 1 + 2 * 1 = 5

public int numTrees(int n) {
    int[] dp = new int[n + 1];
    dp[0] = 1;
    if (n == 0) {
        return 0;
    }
    // 长度为 1 到 n
    for (int len = 1; len <= n; len++) {
        // 将不同的数字作为根节点，只需要考虑到 len
        for (int root = 1; root <= len; root++) {
            int left = root - 1; // 左子树的长度
            int right = len - root; // 右子树的长度
            dp[len] += dp[left] * dp[right];
        }
    }