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才是新的，别的都是指向旧的指针）。

/**
 * 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) {
        if(n==0)
            return vector<TreeNode*>();
        return helper(1,n);
    }
private:
    vector<TreeNode*> helper(int a, int b){
        vector<TreeNode*> res;
        if(a>b){
            res.push_back(nullptr);
        }
        for(int i = a; i<=b;i++){
            auto vL = helper(a,i-1);
            auto vR = helper(i+1,b);
            for(auto ll : vL){
                for(auto rr : vR){
                    TreeNode * root = new TreeNode(i, ll, rr);
                    res.push_back(root);
                }
            }
        }
        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);                可是这样不对， 不知道为什么

错误提示为：

ERROR: AddressSanitizer: stack-use-after-scope on address 0x7ffe12385e00 at pc 0x00000042003f bp 0x7ffe12384f80 sp 0x7ffe12384f78
READ of size 4 at 0x7ffe12385e00 thread T0

HINT: this may be a false positive if your program uses some custom stack unwind mechanism or swapcontext
(longjmp and C++ exceptions are supported)

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

远不如现在的代码；