leetcode 96. 不同的二叉搜索树

递归

n个结点轮流做根节点，然后左右进行递归，两个结果做乘法
发现20个就超int，打表只需要到19

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int numTrees(int n) {
        if(n==0){
            return 1;
        }
        if(n==1 || n==2){
            return n;
        }else{
            int ret = 0;
            for(int i=1;i<=n;i++){
                ret+= numTrees(i-1) * numTrees(n-i);
            }
            return ret;
        }
        return 0;
    }
};
/*
打表
class Solution {
public:
    int numTrees(int n) {
        vector<int> ret = {1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190};
        return ret[n];
    }
};
*/

int main()
{
    Solution Solution1;

    cout << Solution1.numTrees(20) << endl;
    for(int i=0;i<20;i++){
        cout<<Solution1.numTrees(i)<<", ";
    }
    return 0;
}