[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]
分析请参看http://fisherlei.blogspot.com/2013/03/leetcode-unique-binary-search-trees.html
思路是一致的。划分左右子树，然后递归构造。

[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]
写完第一个版本之后，立即发现一个严重的问题。上面的function存在大量的对象拷贝，因为所有变量都是在栈上开辟，所以返回值的时候都需要通过拷贝构造函数来重构vector，面试中这个疏忽是不应该的。

修改版，这里应该用指针及堆来存储变量。

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:       }