95. Unique Binary Search Trees II -----M

Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1 ... n.
Example:
Input: 3
Output:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
Explanation:
The above output corresponds to the 5 unique BST's shown below:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3
 
Constraints:
0 <= n <= 8

A:

难点就在于，左边和右边的子树是相乘关系，而非相加。

 所以，我们这里用了循环，每次create一个新的树（为节省空间，在两个for loop迭代的时候， 新树只有root才是新的，别的都是指向旧的指针）。

为了谨慎起见。多加了很多case来考虑。  重点是，如果某个子树的返回为空，那么就不能直接用for loop了。 ------幸好还是一遍过-----------

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode() : val(0), left(nullptr), right(nullptr) {}

* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

* };

*/

class Solution {

public:

vector<TreeNode*> generateTrees(int n) {

return helper(1,n);

}

private:

vector<TreeNode*> helper(int low, int high){

vector<TreeNode*> res;

for(int val = low; val <= high; val++){

auto vLeft = helper(low, val -1);

auto vRight = helper(val+1, high);

if(vLeft.empty() && vRight.empty()){

auto tmp = new TreeNode(val);

res.push_back(tmp);

}else if (vLeft.empty() && !vRight.empty()){

for(auto rChild : vRight){

auto tmp = new TreeNode(val);

tmp->right = rChild;

res.push_back(tmp);

}

}else if(! vLeft.empty() && vRight.empty()){

for(auto lChild : vLeft){

auto tmp = new TreeNode(val);

tmp->left = lChild;

res.push_back(tmp);

}

}else{ // both are none empty

for(auto lChild : vLeft){

for(auto rChild : vRight){

auto tmp = new TreeNode(val);

tmp->left = lChild;

tmp->right = rChild;

res.push_back(tmp);

}

}

}

}

return res;

}

};

上面的if case太多了。 为了简洁，如果没有子树。 那么 把nullptr 也加入返回结果

class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        return helper(1,n);
    }
private:
    vector<TreeNode*> helper(int low, int high){
        vector<TreeNode*> res;
        if(low > high){
            res.push_back(nullptr);
        }
        for(int val = low; val <= high; val++){
            for(auto lChild : helper(low, val -1)){
                for(auto rChild : helper(val+1, high)){
                    auto tmp = new TreeNode(val, lChild, rChild);
                    res.push_back(tmp);
                }
            }
        }
        return res;
    }
};

Mistakes:
1： 当左边或者右边的子树为空的时候，单纯利用两个for循环是不对的，因为这时候，可以把另一半直接加上就是了。
   这时候，要先判断 size() 是否为0    ----------- 代码见那几个for循环。

2: 当 input 为0，（ 这个，就是题意没讲清楚了）。

Input:	0
Output:	[]
Expected:	[{}]

 -----------当输入为0的时候，输出的结果格式不对，自己试着在all上加个null，也总是报错----
原因是--------- 前面有个return




Learned:

                    TreeNode * root = new TreeNode(i, ll, rr);
                    res.push_back(root);

这几句一开始是这样写的：

                                   TreeNode root(i, ll, rr);

                    res.push_back(&root);                可是这样不对， 不知道为什么

错误： 后者空间放在stack上，会随着函数的结束而销毁。 前者（用new生成的）变量在heap上。可以长久保存

1: 还是要动手写， 光自己在那里，玩儿着想，想不深。 也难以持续。
2： 因为自己本来的代码里面，存在大量的对象数据的拷贝。 其实，是可以仅仅用指针来解决的（虽然这道题目里面，也没有多用多少空间。但当对象大了之后， 还是很显著的）
所以，我原本的代码

for (int i = 0; i < alLeft.size(); i++) {
                    for (int j = 0; j < alRight.size(); j++) {
                        // create a new node, and copy left to right
                        TreeNode tmpTree = createNewTree(rootValue,
                                alLeft.get(i), alRight.get(j));
                        all.add(tmpTree);// add the values rooted at rootValue,
                                            // with one variation of left and
                                            // right child
                    } // end of loop for each of the right side subtree
                } // end of for loop for each of Left side subtree

远不如现在的代码；