题意：输入是n，要求枚举出包含1…n这n个整数的所有二叉搜索树（BST）。
分析：显然这题n不可能很大，考察的是如何枚举每种可能的状态。首先考虑了所有全排列的插入构建BST，发现这样得到的BST有重复。然后发现，若设n的全部BST为T(n)，当根是i时，其左子树的所有可能情况为T(i-1)，右子树的所有可能情况为T(n-i)。这样就可以按n由小到大地递推构造出各个BST了。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
int vvpl=0; vector<vector<TreeNode *>> vvp; vector<TreeNode *> vp; vector<TreeNode *>::iterator it1, end1, it2, end2; TreeNode *mk(TreeNode *p, int d) { if(!p) return 0; TreeNode *q=new TreeNode(p->val+d); q->left=mk(p->left, d); q->right=mk(p->right, d); return q; } class Solution { public: vector<TreeNode *> generateTrees(int n) { int i, j, k, l; TreeNode *p; if(vvpl<=n) { if(vvpl==0) { vvp.push_back(vp); vvp[0].push_back(0); vvpl=1; } for(; vvpl<=n; vvpl++) { vvp.push_back(vp); for(i=1; i<=vvpl; i++) { for(it1=vvp[i-1].begin(), end1=vvp[i-1].end(); it1!=end1; it1++) { for(it2=vvp[vvpl-i].begin(), end2=vvp[vvpl-i].end(); it2!=end2; it2++) { p=new TreeNode(i); p->left=mk(*it1, 0); p->right=mk(*it2, i); vvp[vvpl].push_back(p); } } } } } return vvp[n]; } }; |
ps：LeetCode上面很多这种要求构造出所有可行解的题目，这是之前做的ACM中几乎没有的。虽然题型相对陌生，但解起来也很好玩~