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.
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
» Solve this problem"{1,#,2,3}"
means? > read more on how binary tree is serialized on OJ.[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: }
No comments:
Post a Comment