题目思路

代码

// 方法一：直接用卡特兰数就行 
// 方法二：递归方法
class Solution {
public:
    int numTrees(int n) {
        // 这里把 i当成整个结点，j当成左子树最左侧结点,并一次当根节点尝试
        // f[ i ] = f[ j - 1 - L + 1] * f[ R - (j + 1) + 1] = f[ j - 1] * f[i - j]
        // 其中L = 1, R = j
        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];
    }
};