Given an integer 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
Subscribe to see which companies asked this question.
解题思路：
本题是96.Unique Binary Search Trees的延伸，看网上大神么的解题思路，写的都是“有了96题的解题思路，本题应该不难”，然后给出代码。作为编程小菜的我，想了半天，还是没想出来（心中飘过千万只CNM)。
看完答案以后，总结一下，两道题的核心思想确实一样，都是分治法，但是解题的着眼点真的不一样，96.Unique Binary Search Trees的核心是用DP来求出树的个数，而本题的着眼点是求出所有的树，关键在于如何用递归的方法生成所有的树，如果对递归不熟悉，对如何生成树不熟悉，真的是无从下手。
具体代码如下：
class Solution {
public:
vector<TreeNode*> genBST(int begin, int end)
{
vector<TreeNode*> ret;
if(begin > end) return ret;
for(int i = begin; i <= end; ++i)
{
vector<TreeNode*> l = genBST(begin, i-1);
vector<TreeNode*> r = genBST(i+1,end);
int lSz = l.empty() ? 1 : l.size();
int rSz = r.empty() ? 1 : r.size();
for(int j = 0; j < lSz; ++j)
{
for(int k = 0; k < rSz; ++k)
{
TreeNode* root = new TreeNode(i);
if(l.empty()) root->left =NULL;
else root->left = l[j];
if(r.empty()) root->right = NULL;
else root->right = r[k];
root-> val = i;
ret.push_back(root);
}
}
}
return ret;
}
vector<TreeNode*> generateTrees(int n) {
return genBST(1,n);
}
};
