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的延伸胃夏，看網(wǎng)上大神么的解題思路，寫的都是“有了96題的解題思路瓶盛，本題應(yīng)該不難”椭符，然后給出代碼徙融。作為編程小菜的我，想了半天砖茸，還是沒(méi)想出來(lái)（心中飄過(guò)千萬(wàn)只CNM)酵镜。
看完答案以后碉碉，總結(jié)一下，兩道題的核心思想確實(shí)一樣淮韭，都是分治法垢粮，但是解題的著眼點(diǎn)真的不一樣，96.Unique Binary Search Trees的核心是用DP來(lái)求出樹的個(gè)數(shù)靠粪，而本題的著眼點(diǎn)是求出所有的樹蜡吧，關(guān)鍵在于如何用遞歸的方法生成所有的樹，如果對(duì)遞歸不熟悉占键，對(duì)如何生成樹不熟悉昔善，真的是無(wú)從下手。
具體代碼如下：
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);
}
};
