分析

• 本题的考点：递推、卡特兰数。

• n个节点1~n，当选定第i个节点为根节点时，左侧1~i-1是其左子树中的节点，右侧i+1~n是其右子树中的节点，因此对于选定根节点为i可以形成$f(i-1) \times f(n-i)$棵二叉树。

• n个结点的二叉树数量f(n) ，则有递推公式，即：
  $$ f(n) = \sum _{i=1}^{n} f(i-1) \times f(n-i) \quad \quad f(0)=1 $$

• 可以推出：

$$ f(n) = C_{2n}^{n} - C_{2n}^{n-1} = \frac{C_{2n} ^ n}{n+1} $$

• 具体关于卡特兰数的讲解可以参考：网址。

代码

• C++

class Solution {
public:
    int numTrees(int n) {

        // f[i]: 表示一共i个不同的节点可以组成的二叉搜索树的个数
        vector<int> f(n + 1);
        f[0] = 1;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= i; j++)
                f[i] += f[j - 1] * f[i - j];
        return f[n];
    }
};

• Java

class Solution {
    public int numTrees(int n) {

        // f[i]: 表示一共i个不同的节点可以组成的二叉搜索树的个数
        int[] f = new int[n + 1];
        f[0] = 1;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= i; j++)
                f[i] += f[j - 1] * f[i - j];
        return f[n];
    }
}

时空复杂度分析

• 时间复杂度：$O(n^2)$。

• 空间复杂度：$O(n)$。