Unique Binary Search Trees II

class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        if (n==0) return vector<TreeNode*>();
        return genTree(1, n);
    }
    
    vector<TreeNode*> genTree(int start, int end) {
        // all generated trees from start to end
        vector<TreeNode*> tree_list;
        if (start>end) tree_list.push_back(NULL);
        
        for(int i=start;i<=end;++i) {
            // each can be root
            // recursively generate left subtree
            vector<TreeNode*> left = genTree(start, i-1);
            // recursively generate right subtree
            vector<TreeNode*> right = genTree(i+1, end);

            // combine left and right subtrees with i as root
            for(auto lnode : left) {
                for(auto rnode : right) {
                    TreeNode* root = new TreeNode(i);
                    root->left = lnode;
                    root->right = rnode;
                    // add to result and return
                    tree_list.push_back(root);
                }
            }
        }
        return tree_list;
    }
};