Unique Binary Search Trees II

Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.

Example

Given n = 3, your program should return all 5 unique BST's shown below.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

class Solution {
    vector<TreeNode *> generateTrees(int start, int end) {
        vector<TreeNode *> output;
        if (start > end) {
            output.push_back(NULL);
            return output;
        }
        
        for(int i = start; i <=end; i++) {
            vector<TreeNode *> leftSubTrees = generateTrees(start, i-1);
            vector<TreeNode *> rightSubTrees = generateTrees(i+1, end);
            for(TreeNode *left : leftSubTrees)
                for(TreeNode *right : rightSubTrees) {
                     TreeNode *root = new TreeNode(i);
                     root->left = left;
                     root->right = right;
                     output.push_back(root);
                }
             
        }
        return output;
    }
    
public:

    /**
     * @paramn n: An integer
     * @return: A list of root
     */
    vector<TreeNode *> generateTrees(int n) {
        return generateTrees(1, n);
    }
};

class Solution {
    TreeNode * clone(TreeNode *root, int adjust) {
         TreeNode *newRoot = NULL;
         
         if (root) {
             newRoot = new TreeNode(root->val + adjust);
             newRoot->left = clone(root->left, adjust);
             newRoot->right = clone(root->right, adjust);
         }
         
         return newRoot;
    }
    
public:

    /**
     * @paramn n: An integer
     * @return: A list of root
     */
    vector<TreeNode *> generateTrees(int n) {
        vector<vector<TreeNode *>> Gens(n+1);
        Gens[0].push_back(NULL);
        
        for(int i = 1; i <=n; i++) {
            for(int j = 1; j <= i; j++) {
                    for(TreeNode *left : Gens[j-1])
                        for(TreeNode *right : Gens[i-j]) {
                            TreeNode *root = new TreeNode(j);
                            root->left = clone(left, 0);
                            root->right = clone(right, j);
                            Gens[i].push_back(root);
                        }
            }
        }
        
        return Gens[n];
    }
};