Unique Binary Search Trees II

来源：Leetcode

原帖：http://oj.leetcode.com/problems/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

代码：

 class Solution {  
 public:  
   vector<TreeNode*> generateTrees(int n) {  
     return generateTreesHelper(1, n);  
   }  
   
   vector<TreeNode*> generateTreesHelper(int start, int end) { // 1...n, left = 1, right = n  
     vector<TreeNode*> res;  
     if (start > end) {  
       res.push_back(NULL);  
       return res;  
     }  
     for (int k = start; k <= end; k++) { // root starts from k; 拆分成不同left, right subtree  
       auto leftTrees = generateTreesHelper(start, k - 1);  
       auto rightTrees = generateTreesHelper(k + 1, end);  
       for (int i = 0; i < leftTrees.size(); i++) {  
         for (int j = 0; j < rightTrees.size(); j++) {  
           TreeNode* root = new TreeNode(k);  
           root->left = leftTrees[i]; // concatenate into left or right  
           root->right = rightTrees[j];  
           res.push_back(root);  
         }  
       }  
     }  
     return res;  
   }  
 };