首页 > 代码库 > [LeetCode]Unique Binary Search TreesII
[LeetCode]Unique Binary Search TreesII
题目：Unique Binary Search TreesII
如果要列出所有可能的二叉搜索树，可以在上面的思路上进一步。
f(n) = f(0)*f(n-1) + f(1)*f(n-2) + ... + f(n-1)*f(0);
只要求出不同变量下的子树的所有情况，在整合到一起就可以了。
具体思路：
1.外循环遍历树根可能数值k(m->n);
2.分别求左右子树，左子树的可能取值范围（m->k-1）,右子树的可能取值范围（k+1->n）；
注意左右子树可能为空，此时后面合并的时候要分开考虑，因为合并的时候是双重循环，外循环可能为空导致内循环的数据没有机会遍历；
3.最后整合，以当前值k为树根，把左右子树加进去。但是若左子树是l种情况，右子树是r种情况，一共是l*r种情况。
4.以上整个过程用递归描述，递归以当前给的范围来做树根。退出条件是范围内仅有一个可能数值，将它做树根直接返回。
注意：
1.n==0的情况单独考虑
2.左右子树可能为空。
1 vector<TreeNode*> generateTrees(int n){
2 vector<TreeNode *>trees;
3 if (!n){//n==0时，空树
4 trees.push_back(NULL);
5 return trees;
6 }
7 pair<int, int> border(1,n);
8 generateTreeNum(trees,border);
9 return trees;
10 }
11
12 void generateTreeNum(vector<TreeNode *> &trees, pair<int, int>border){
13 if (border.first == border.second){
14 TreeNode *root = new TreeNode(border.first);
15 trees.push_back(root);
16 return;
17 }
18 for (int i = border.first; i <= border.second; i++)
19 {
20 vector<TreeNode *> lchild;
21 if (i != border.first){//递归求左子树
22 pair<int, int> p(border.first,i - 1);
23 generateTreeNum(lchild, p);
24 }
25 vector<TreeNode *> rchild;
26 if (i != border.second){//递归求右子树
27 pair<int, int> p(i + 1, border.second);
28 generateTreeNum(rchild, p);
29 }
30 if (!lchild.size()){//左子树为空,树根必定为border.first
31 vector<TreeNode *>::iterator it = rchild.begin();
32 while (it != rchild.end()){
33 TreeNode *root = new TreeNode(border.first);
34 root->right = (*it);
35 trees.push_back(root);
36 ++it;
37 }
38 }
39 else if (!rchild.size()){//右子树为空,树根必定为border.second
40 vector<TreeNode *>::iterator it = lchild.begin();
41 while (it != lchild.end()){
42 TreeNode *root = new TreeNode(border.second);
43 root->left = (*it);
44 trees.push_back(root);
45 ++it;
46 }
47 }
48 else{
49 vector<TreeNode *>::iterator lit = lchild.begin();
50 vector<TreeNode *>::iterator rit = rchild.begin();
51 while (lit != lchild.end()){
52 TreeNode *root = new TreeNode(i);
53 root->left = (*lit);
54 root->right = (*rit);
55 trees.push_back(root);
56 ++rit;//内循环递增右子树的情况
57 if (rit == rchild.end()){
58 ++lit;//外循环递增左子树的情况
59 rit = rchild.begin();
60 }
61 }
62 }
63 }
64 }
[LeetCode]Unique Binary Search TreesII
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。