Unique Binary Search Trees Solutions in C++

// Source : https://oj.leetcode.com/problems/unique-binary-search-trees/
// Author : Hao Chen
// Date   : 2014-06-25



#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int numTrees1(int n) ;
int numTrees2(int n) ;

int numTrees(int n) {
    return numTrees1(n);
}

int numTrees1(int n) {
    int *cnt = (int*)malloc((n+1)*sizeof(int));
    memset(cnt, 0, (n+1)*sizeof(int));
    cnt[0] = 1;
    cnt[1] = 1;
    
    for (int i=2; i<=n; i++){
        for(int j=0; j<i; j++){
           cnt[i] += cnt[j]*cnt[i-j-1];
        }
    }
    int sum = cnt[n];
    free(cnt);
    return sum;
}



int numTrees2(int n) {
    if (n<=0) return 0;
    if (n == 1 ) return 1;
    int sum=0;
    for (int i=1; i<=n; i++){
        if (i==1||i==n){
            sum += numTrees(n-1);
        }else{
            sum += (numTrees(i-1) * numTrees(n-i));
        }
    }
    return sum;
}


int main(int argc, char** argv) 
{
    int n=2;
    if (argc>1){
        n = atoi(argv[1]);
    }
    printf("%d=%d\n", n, numTrees(n));
    return 0;
}

#include <climits>

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

/// Source : https://leetcode.com/problems/unique-binary-search-trees/description/
/// Author : liuyubobobo
/// Time   : 2018-09-10

#include <iostream>
#include <vector>

using namespace std;


/// Memory Search
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {

public:
    int numTrees(int n) {

        vector<int> dp(n + 1, -1);
        return numTrees(n, dp);
    }

private:
    int numTrees(int n, vector<int>& dp){

        if(n <= 1)
            return 1;

        if(dp[n] != -1)
            return dp[n];

        int res = 0;
        for(int i = 1; i <= n; i ++)
            res += numTrees(i - 1, dp) * numTrees(n - i, dp);
        return dp[n] = res;
    }
};


int main() {

    cout << Solution().numTrees(3) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/unique-binary-search-trees/description/
/// Author : liuyubobobo
/// Time   : 2018-09-10

#include <iostream>
#include <vector>

using namespace std;


/// Dynamic Programming
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {

public:
    int numTrees(int n) {

        vector<int> dp(n + 1, 0);
        dp[0] = dp[1] = 1;
        for(int i = 2; i <= n; i ++)
            for(int j = 1; j <= i; j ++)
                dp[i] += dp[j - 1] * dp[i - j];
        return dp[n];
    }
};


int main() {

    cout << Solution().numTrees(3) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/unique-binary-search-trees/description/
/// Author : liuyubobobo
/// Time   : 2018-09-10

#include <iostream>
#include <vector>

using namespace std;


/// Mathematics
/// It's Catalan Number!
/// See more about Catalan number here:
/// https://en.wikipedia.org/wiki/Catalan_number
///
/// Time Complexity: O(n)
/// Space Complexity: O(1)

class Solution {

public:
    int numTrees(int n) {

        long long C = 1ll;
        for(int i = 0; i < n; i ++)
            C = C * 2 * (2 * i + 1) / (i + 2);
        return C;
    }
};


int main() {

    cout << Solution().numTrees(3) << endl;

    return 0;
}