leetCode.96. 不同的二叉搜索树

题目思路

代码

// 方法一：直接用卡特兰数就行 
// 方法二：递归方法
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 = jvector<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];}
};