LeetCode Problem : Unique Binary Search Trees II

Problem

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

For 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
confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.


OJ's Binary Tree Serialization:
The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.

Here's an example:
   1
  / \
 2   3
    /
   4
    \
     5
The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

Code

vector<TreeNode *> gt_r(int l,int r)
{
    if(l > r){
        vector<TreeNode *> tmp(1);
        tmp[0] = 0;
        return tmp;
    }
    vector<TreeNode *> result;
    for(int i = l;i <= r;++i){
        vector<TreeNode *> lt = gt_r(l,i - 1);
        vector<TreeNode *> rt = gt_r(i + 1,r);
        int m = lt.size();
        int n = rt.size();
        for(int j = 0;j < m;++j){
            for(int k = 0;k < n;++k){
                TreeNode *p = new TreeNode(i);
                p->left = lt[j];
                p->right = rt[k];
                result.push_back(p);
            }
        }
    }
return result;
}
vector<TreeNode *> generateTrees(int n) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
    return gt_r(1,n);
}