95_UniqueBST_II.cpp

#include<string.h>
#include <set>
#include<vector>
#include<iostream>
#include<map>
#include<stack>
#include <unordered_set>
#include <algorithm>    // std::min_element, std::max_element
using namespace std;

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

TreeNode* clone(TreeNode* root)
{
    if (root == nullptr)
        return nullptr;
    TreeNode* newroot = new TreeNode(root->val);
    newroot->left = clone(root->left);
    newroot->right = clone(root->right);
    return newroot;
}
vector<TreeNode*> generateTrees(int n) {
    vector<TreeNode*> res(1, nullptr);
    for (int i = 1; i <= n; i++) {
        vector<TreeNode*> tmp;
        for (int j = 0; j < res.size(); j++) {
            TreeNode* oldroot = res[j];
            TreeNode* root = new TreeNode(i);
            TreeNode* target = clone(oldroot);
            root->left = target;
            tmp.push_back(root);

            if (oldroot != nullptr)
            {
                TreeNode* tmpold = oldroot;
                while (tmpold->right != nullptr)
                {
                    TreeNode* nonroot = new TreeNode(i);
                    TreeNode* tright = tmpold->right;
                    tmpold->right = nonroot;
                    nonroot->left = tright;
                    TreeNode* target = clone(oldroot);
                    tmp.push_back(target);
                    tmpold->right = tright;
                    tmpold = tmpold->right;
                }
                tmpold->right = new TreeNode(i);
                TreeNode* target = clone(oldroot);
                tmp.push_back(target);
                tmpold->right = nullptr;
            }
        }
        res = tmp;
    }
    return res;
}

int main95()
{
    vector<TreeNode*> res =  generateTrees(3);
    return 0;
}