a***e
发帖数: 413 | 1 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 generateTrees(int n) {
if (n==0) return generate(1,0);
return generate(1,n);
}
private:
vector generate(int start, int end){
vector subTree;
if (start>end){
subTree.push_back(NULL);
return subTree;
}
for (int k=start; k<=end; k++){
vector leftSubs = generate(start, k-1);
vector rightSubs = generate(k+1, end);
for (auto i: leftSubs){
for (auto j:rightSubs){
TreeNode *node = new TreeNode(k);
node->left = i;
node->right = j;
subTree.push_back(node);
}
}
}
return subTree;
}
}; |
|
