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

1 /** 2  * Definition for binary tree 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 class Solution {11 public:12     vector
     
       generateTrees(int n) {13         // Start typing your C/C++ solution below14         // DO NOT write int main() function15         return generateTrees(1, n);16     }17     18      vector
      
        generateTrees(int start, int end) 19     {20         // If the range is invalid, then return an empty tree21         vector
       
         result;22         23         if (start > end) 24         {25             result.push_back(NULL);26             return result;27         }28 29         30         for (int i = start; i <= end; ++i) {31             // Generate all possible left subtrees (including the empty subtree)32             vector
        
          leftSubtrees = generateTrees(start, i - 1);33 34             // Generate all possible right subtrees (including the empty subtree)35             vector
         
           rightSubtrees = generateTrees(i + 1, end);36 37             // For each left subtree and each right subtree, create a root node38             // with value i and then link the two subtrees to the root39             for (int j = 0; j < leftSubtrees.size(); ++j) {40                 for (int k = 0; k < rightSubtrees.size(); ++k) {41                     TreeNode *root = new TreeNode(i);42                     root->left = leftSubtrees[j];43                     root->right = rightSubtrees[k];44                     result.push_back(root);45                 }46             }47         }48         return result;49     }50     51 };