【leetcode】 Unique Binary Search Trees II

问题可以归结为：给定一颗有节点【1--n-1】组成 的任意一颗搜索二叉树，现往里面插入一个节点，形成一个新的搜索二叉树。

class Solution {
public:

    TreeNode *clonetree(TreeNode *a){
        TreeNode *b = new TreeNode(a->val);
        if(a->left) b->left = clonetree(a->left);
        if(a->right) b->right = clonetree(a->right);
        return b;
    }
    vector<TreeNode *> generateTrees(int n) {
        TreeNode *nowright;
        TreeNode *tmpnode;
        vector<TreeNode *> Res;
        if(n==0) {
            Res.push_back(NULL);
            return Res;
        }
        vector<TreeNode *> tmp;
        TreeNode *a = new TreeNode(1);
        Res.push_back(a);
        for(int i=2; i<=n; i++){
            while(!Res.empty()){
                a = Res.back();
                Res.pop_back();
                TreeNode *newhead = new TreeNode(i);
                newhead->left = a;
                tmp.push_back(newhead);
                nowright = a;
                while(1){
                    TreeNode *b;
                    b = clonetree(a);
                    TreeNode *newnode = new TreeNode(i);
                    tmpnode = b;
                    while(tmpnode->val != nowright->val) tmpnode = tmpnode->right;
                    newnode->left = tmpnode->right;
                    tmpnode->right = newnode;
                    tmp.push_back(b);
                    nowright = nowright->right;
                    if(nowright == NULL) break;
                }
            }
            Res.swap(tmp);
        }
        return Res;
    }
}