leetcode

题目：Unique Binary Search Trees II

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

这道题是Unique Binary Search Trees I的后续，可以先看看http://www.cnblogs.com/laihaiteng/p/3789279.html这个，思路上有相似的地方

个人思路：

1、还是从1-n逐个遍历，作为BST的根节点，左半部分作为根节点的左子树，右半部分作为根节点的右子树

2、递归函数返回从start到end的节点所能产生的不同的BST的集合，则把不同的左BST与右BST做一个乘积（或者说一一匹配），就是此时某个i（1-n中的某个数）作为根节点的BST的集合

代码：

 1 #include <stddef.h>
 2 #include <vector>
 3 
 4 using namespace std;
 5 
 6 struct TreeNode
 7 {
 8     int val;
 9     TreeNode *left;
10     TreeNode *right;
11     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
12 };
13 
14 class Solution
15 {
16 public:
17     vector<TreeNode *> generateTrees(int n)
18     {
19         vector<TreeNode *> result;
20 
21         if (n < 1)
22         {
23             TreeNode *root = NULL;
24             result.push_back(root);
25             return result;
26         }
27 
28         result = generatePartTrees(1, n);
29 
30         return result;
31     }
32 private:
33     vector<TreeNode *> generatePartTrees(int start, int end)
34     {
35         vector<TreeNode *> part;
36 
37         for (int i = start; i <= end; ++i)
38         {
39             vector<TreeNode *> leftTrees = generatePartTrees(start, i - 1);
40             vector<TreeNode *> rightTrees = generatePartTrees(i + 1, end);
41             //左右子树非空
42             if (!leftTrees.empty() && !rightTrees.empty())
43             {
44                 for (int x = 0; x < leftTrees.size(); ++x)
45                 {
46                     for (int y = 0; y < rightTrees.size(); ++y)
47                     {
48                         TreeNode *root = new TreeNode(i);
49                         TreeNode *left = leftTrees[x];
50                         root->left = left;
51                         TreeNode *right = rightTrees[y];
52                         root->right = right;
53                         part.push_back(root);
54                     }
55                 }
56             }
57             //左子树非空，右子树为空
58             if (!leftTrees.empty() && rightTrees.empty())
59             {
60                 for (int x = 0; x < leftTrees.size(); ++x)
61                 {
62                     TreeNode *root = new TreeNode(i);
63                     TreeNode *left = leftTrees[x];
64                     root->left = left;
65                     root->right = NULL;
66                     part.push_back(root);
67                 }
68             }
69             //左子树为空，右子树非空
70             if (leftTrees.empty() && !rightTrees.empty())
71             {
72                 for (int y = 0; y < rightTrees.size(); ++y)
73                 {
74                     TreeNode *root = new TreeNode(i);
75                     TreeNode *right = rightTrees[y];
76                     root->left = NULL;
77                     root->right = right;
78                     part.push_back(root);
79                 }
80             }
81             //左右子树均为空
82             if (leftTrees.empty() && rightTrees.empty())
83             {
84                 TreeNode *root = new TreeNode(i);
85                 root->left = NULL;
86                 root->right = NULL;
87                 part.push_back(root);
88             }
89         }
90 
91         return part;
92     }
93 };

View Code

网上看了一下，大致都是这个思路，但发现有更好的写法，链接：http://www.cnblogs.com/remlostime/archive/2012/11/19/2777841.html

精简了一下代码：

 1 #include <stddef.h>
 2 #include <vector>
 3 
 4 using namespace std;
 5 
 6 struct TreeNode
 7 {
 8     int val;
 9     TreeNode *left;
10     TreeNode *right;
11     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
12 };
13 
14 class Solution
15 {
16 public:
17     vector<TreeNode *> generateTrees(int n)
18     {
19         return generatePartTrees(1, n);
20     }
21 private:
22     vector<TreeNode *> generatePartTrees(int start, int end)
23     {
24         vector<TreeNode *> part;
25 
26         if (start > end)
27         {
28             part.push_back(NULL);
29             return part;
30         }
31 
32         for (int i = start; i <= end; ++i)
33         {
34             vector<TreeNode *> leftTrees = generatePartTrees(start, i - 1);
35             vector<TreeNode *> rightTrees = generatePartTrees(i + 1, end);
36             for (int x = 0; x < leftTrees.size(); ++x)
37             {
38                 for (int y = 0; y < rightTrees.size(); ++y)
39                 {
40                     TreeNode *root = new TreeNode(i);
41                     TreeNode *left = leftTrees[x];
42                     root->left = left;
43                     TreeNode *right = rightTrees[y];
44                     root->right = right;
45                     part.push_back(root);
46                 }
47             }
48         }
49 
50         return part;
51     }
52 };

View Code