## Wednesday, March 20, 2013

### [LeetCode] Unique Binary Search Trees II, Solution

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.
» Solve this problem

[Thoughts]

[Code]
``````1:       vector<TreeNode *> generateTrees(int n) {
2:            if(n ==0) return generate(1,0);
3:            return generate(1, n);
4:       }
5:       vector<TreeNode *> generate(int start, int end)
6:       {
7:            vector<TreeNode *> subTree;
8:            if(start>end)
9:            {
10:                 subTree.push_back(NULL);
11:                 return subTree;
12:            }
13:            for(int i =start; i<=end; i++)
14:            {
15:                 vector<TreeNode*> leftSubs = generate(start, i-1);
16:                 vector<TreeNode*> rightSubs = generate(i+1, end);
17:                 for(int j = 0; j< leftSubs.size(); j++)
18:                 {
19:                      for(int k=0; k<rightSubs.size(); k++)
20:                      {
21:                           TreeNode *node = new TreeNode(i);
22:                           node->left = leftSubs[j];
23:                           node->right = rightSubs[k];
24:                           subTree.push_back(node);
25:                      }
26:                 }
27:            }
28:            return subTree;
29:       }
``````

[Note]

``````1:       vector<TreeNode *> generateTrees(int n) {
2:            if(n ==0) return *generate(1,0);
3:            return *generate(1, n);
4:       }
5:       vector<TreeNode *>* generate(int start, int end)
6:       {
7:            vector<TreeNode *> *subTree = new vector<TreeNode*>();
8:            if(start>end)
9:            {
10:                 subTree->push_back(NULL);
11:                 return subTree;
12:            }
13:            for(int i =start; i<=end; i++)
14:            {
15:                 vector<TreeNode*> *leftSubs = generate(start, i-1);
16:                 vector<TreeNode*> *rightSubs = generate(i+1, end);
17:                 for(int j = 0; j< leftSubs->size(); j++)
18:                 {
19:                      for(int k=0; k<rightSubs->size(); k++)
20:                      {
21:                           TreeNode *node = new TreeNode(i);
22:                           node->left = (*leftSubs)[j];
23:                           node->right = (*rightSubs)[k];
24:                           subTree->push_back(node);
25:                      }
26:                 }
27:            }
28:            return subTree;
29:       }
``````