經典中的經典Unique Binary Search Trees II

經典中的經典Unique Binary Search Trees II

Unique Binary Search Trees II

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

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector generateTrees(int n) {
        return helper(1, n);
    }
    vector helper(int s, int e){
        if(s>e){
            return vector(1, NULL);
        }
        
        vector res;
        for(int i=s; i<=e; i++){
            vector left=helper(s, i-1);
            vector right=helper(i+1, e);
            for(int j=0; jleft=left[j];
                    p->right=right[k];
                    res.push_back(p);
                }
            }
        }
        return res;
    }
};