95. Unique Binary Search Trees II

At root i with nodes [s, e] (s <= i <= e), we can divide this problem into two subproblems: 1. build left subtrees with nodes [s, i-1]; 2. build right subtrees with nodes[i+1, e]. After achieving these subtrees, we conquer the subtrees to form the solution at root i.

1:  class Solution {  
2:  public:  
3:    vector<TreeNode*> generateTrees(int n) {  
4:      if (n == 0) return vector<TreeNode*>(0, 0);  
5:      return helper(1, n);  
6:    }  
7:    vector<TreeNode*> helper(int s, int e) {  
8:      vector<TreeNode*> res;  
9:      if (s > e) {  
10:        res.push_back(NULL);  
11:        return res;  
12:      }  
13:      for (int i = s; i <= e; i++) {  
14:        vector<TreeNode*> left = helper(s, i-1);  
15:        vector<TreeNode*> right = helper(i+1, e);  
16:        for (int j = 0; j < left.size(); j++) {  
17:          for (int k = 0; k < right.size(); k++) {  
18:            TreeNode *tn = new TreeNode(i);  
19:            tn->left = left[j];  
20:            tn->right = right[k];  
21:            res.push_back(tn);  
22:          }  
23:        }  
24:      }  
25:      return res;  
26:    }  
27:  };  

There is DP solution in the top rated solution. Need to investigate later.