leetcode--95. Unique Binary Search Trees II

95. Unique Binary Search Trees II

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

2、思路：II与I是一样的题目只是返回结果不同，I只需要返回可以生成的BST的数目，II要求返回所有Tree。II的难点在于怎么返回这个结果。基本代码思路还是I，[st, i - 1]和[i+1, end]

返回以此为范围生成的所有tree，然后两者合并，当然合并时需要把每棵树都要copy一份。

3、代码实现

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     vector<TreeNode*> generateTrees(int n) {
13         return generate_bst(1, n);
14     }
15     
16     vector<TreeNode*> generate_bst(int st, int end) {
17         vector<TreeNode*> results;
18         for (int i = st; i <= end; i++) {
19             vector<TreeNode*> res_left = generate_bst(st, i - 1);
20             vector<TreeNode*> res_right = generate_bst(i + 1, end);
21             save_results(results, i, res_left, res_right);
22         }
23         return results;
24     }
25     
26     void save_results(vector<TreeNode*>& results, const int root_val, 
27                       const vector<TreeNode*>& res_left, const vector<TreeNode*>& res_right) {
28         int num_left = res_left.size();
29         int num_right = res_right.size();
30         if (num_left == 0 && num_right == 0) {
31             TreeNode* root = new TreeNode(root_val);
32             return results.push_back(root);
33         } else if (num_left == 0) {
34             for (int i = 0; i < num_right; i++) {
35                 TreeNode* root = new TreeNode(root_val);
36                 root->right = copy_tree(res_right[i]);
37                 results.push_back(root);
38             }
39         } else if (num_right == 0) {
40             for (int i = 0; i < num_left; i++) {
41                 TreeNode* root = new TreeNode(root_val);
42                 root->left = copy_tree(res_left[i]);
43                 results.push_back(root);
44             }
45         } else {
46             for (int i = 0; i < num_left; i++) {
47                 for (int j = 0; j < num_right; j++) {
48                     TreeNode* root = new TreeNode(root_val);
49                     root->left = copy_tree(res_left[i]);
50                     root->right = copy_tree(res_right[j]);
51                     results.push_back(root);
52                 }
53             }
54         }
55         return;
56     }
57     
58     TreeNode* copy_tree(TreeNode* root) {
59         if (root == NULL) {
60             return NULL;
61         }
62         
63         TreeNode* node = new TreeNode(root->val);
64         node->left = copy_tree(root->left);
65         node->right = copy_tree(root->right);
66         return node;
67     }
68 };

View Code

4、优化

应该是没有优化空间了，返回结果决定了解空间，后续看看在一些小操作上面有没有优化空间。

5、api

verctor： push_back只能在最后追加(添加)一个元素。似乎没有方法能一次添加多个元素，除了初始化时。