lintcode- 不同的二叉树II

解法思路：

要生成所有情况的二叉树，首先肯定能想到遍历所有的数作为头结点的情况，构建头结点的左右子树的过程可以利用递归完成。此处难点应该在于 (1)同一个数作为头结点时，子树可以有不同的结构；(2) 当前树已经构造完成，应该将头结点加入到结果vector中。

此处的解决办法：递归的正常解法，从上往下递归，从下往上构造，在构造过程中，将左右子树的所有情况都存在l,r两个vector<TreeNode*> 中，然后双重循环，两两组合，作为当前节点的左右孩子，每一种组合就是一种树的结构，将当前节点作为子树的根存在res中，返回给上一层。

注意： 因为res是在每次递归过程中申请的，只存储本层子树的根节点，并且返回给上一层，作为上一层节点的左孩子或者右孩子。在最上层的res中，只存储了每个不同的树的根节点。

vector<TreeNode*> generateTreeTmp(int beg, int ends){
        vector<TreeNode*> res;     //每次进入递归都是申请一个新的res,在返回以后这个res就会被释放掉
        if(beg > ends){
            res.push_back(NULL);
            return res;
        }
        if(beg == ends){            //当区间中只有一个数时，将构造出的节点直接加入到res中，返回res
            res.push_back(new TreeNode(beg));
            return res;
        }
        for(int i=beg; i<=ends; ++i){       //对于从beg到ends,每个数都要作为根节点       
            vector<TreeNode*> l = generateTreeTmp(beg, i-1);  //接受下层已经构造好的各种子树的情况
            vector<TreeNode*> r = generateTreeTmp(i+1, ends);
            for(int j=0; j<l.size(); ++j){   //对于当前根节点，左右子树的每种情况与根节点进行链接，然后将根节点加入到本层res中
                for(int k=0; k<r.size(); ++k){
                    TreeNode* root = new TreeNode(i);
                    root->left = l[j];
                    root->right = r[k];
                    res.push_back(root);
                }
            }
        }
        return res;
    }
vector<TreeNode *> generateTrees(int n) {
        // write your code here
        vector<TreeNode*> res = generateTreeTmp(1, n);
        return res;
    }

本题解法参照https://blog.csdn.net/wangyuquanliuli/article/details/45793043，只是感觉没有注释，稍微标记一下。