Unique Binary Search Trees II Solutions in C++

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



#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

vector<TreeNode*> generateTrees(int low, int high);

vector<TreeNode*> generateTrees(int n) {

    vector<TreeNode*> v;
    v = generateTrees(1, n);
    return v;
}

vector<TreeNode*> generateTrees(int low, int high){
    vector<TreeNode*> v;
    if (low > high || low<=0 || high<=0){
        v.push_back(NULL);
        return v;
    }
    if (low==high){
        TreeNode* node = new TreeNode(low);
        v.push_back(node); 
        return v;
    }
    for (int i=low; i <= high; i++){
        vector<TreeNode*> vleft = generateTrees(low, i-1);
        vector<TreeNode*> vright = generateTrees(i+1, high);
        for (int l=0; l<vleft.size(); l++){
            for (int r=0; r<vright.size(); r++){
                TreeNode *root = new TreeNode(i);
                root->left = vleft[l];
                root->right = vright[r];
                v.push_back(root);
            }
        }
    }
    return v;
}

void printTree(TreeNode *root){
    if (root == NULL){
        printf("# ");
        return;
    }
    printf("%d ", root->val );

    printTree(root->left);
    printTree(root->right);
}


int main(int argc, char** argv) 
{
    int n=2;
    if (argc>1){
        n = atoi(argv[1]);
    }
    vector<TreeNode*> v = generateTrees(n);
    for(int i=0; i<v.size(); i++){
        printTree(v[i]);
        printf("\n");
    }
    return 0;
}

#include <vector>
#include <cstddef>

using std::vector;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
}; 

class Solution {
public:
    vector<TreeNode *> generateTrees(int n) {
        return generateTrees(1, n+1);
    }
    vector<TreeNode *> generateTrees(int b, int e) {
        if (e-b < 2) return vector<TreeNode *>{e-b ? new TreeNode(b) : NULL};
        vector<TreeNode *> retv;
        for (int i=b; i<e; ++i) {
            vector<TreeNode *> retLeft = generateTrees(b, i);
            vector<TreeNode *> retRight = generateTrees(i+1, e);
            for (auto pL : retLeft)
                for (auto pR : retRight) {
                    TreeNode *root = new TreeNode(i);
                    root->left = pL;
                    root->right = pR;
                    retv.push_back(root);
                }
        }
        return retv;
    }    
};

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

#include <iostream>
#include <vector>

using namespace std;

/// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

/// Backtracking
/// Time Complexity: O(n^n)
/// Space Complexity: O(n^n)
class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {

        vector<int> vals;
        for(int i = 1; i <= n; i ++)
            vals.push_back(i);
        return generateTrees(vals);
    }

private:
    vector<TreeNode*> generateTrees(const vector<int>& vec){

        if(vec.size() == 0)
            return {};

        if(vec.size() == 1)
            return {new TreeNode(vec[0])};

        vector<TreeNode*> ret;
        for(int i = 0; i < vec.size(); i ++){
            vector<TreeNode*> left = generateTrees(vector<int>(vec.begin(), vec.begin() + i));
            vector<TreeNode*> right = generateTrees(vector<int>(vec.begin() + i + 1, vec.end()));
            if(left.empty()) left.push_back(NULL);
            if(right.empty()) right.push_back(NULL);

            for(TreeNode* ltree: left)
                for(TreeNode* rtree: right){
                    TreeNode* root = new TreeNode(vec[i]);
                    root->left = ltree;
                    root->right = rtree;
                    ret.push_back(root);
                }
        }
        return ret;
    }
};


int main() {

    cout << Solution().generateTrees(0).size() << endl;
    cout << Solution().generateTrees(3).size() << endl;

    return 0;
}