不同的二叉搜索树

假设n个节点存在二叉排序树的个数是G(n)，1为根节点，2为根节点，…，n为根节点，当1为根节点时，其左子树节点个数为0，右子树节点个数为n-1，同理当2为根节点时，其左子树节点个数为1，右子树节点为n-2，所以可得$G(n)=G(0)G(n-1)+G(1)G(n-2)+…+G(n-1)G(0)$，即$G(n)=\sum_{i=1}^nG(i-1)G(n-i)$。

可以根据此递推公式求解，但更进一步可以知道这是卡特兰数的n阶递推公式，可以化简为1阶递推公式：$G(n+1)=\cfrac{2(2n+1)}{n+2}G(n)$。其中$G(0)=1$。

class Solution {
public:
    int numTrees(int n) {
        long long G = 1;
        for (int i = 0; i < n; ++i) {
            G = G * 2 * (2 * i + 1) / (i + 2);
        }
        return (int)G;
    }
};

复杂度分析：

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

1	class Solution {
2	public:
3	int numTrees(int n) {
4	long long G = 1;
5	for (int i = 0; i < n; ++i) {
6	G = G * 2 * (2 * i + 1) / (i + 2);
7	}
8	return (int)G;
9	}
10	};