/**
 * 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*>res;
    int n;
    vector<TreeNode*> generateTrees(int n) {
        if(n==0)return res;
        this->n=n;
        dfs(1,0,NULL);
        return res;
    }
    
    void dfs(int N,int level,TreeNode* root){
        TreeNode *node=new TreeNode(N);
        
        if(level==0){
            node->left=root;
            root=node;
        }
        else{
            TreeNode *temp=root;
            for(int i=0;i<level-1;i++){
                temp=temp->right;
            }
            node->left=temp->right;
            temp->right=node;
        }
        
        if(N==n){
            res.push_back(root);
            return;
        }
        
        
        for(int i=0;i<=level+1;i++){
            TreeNode *copy=new TreeNode(root->val);
            copy1(copy,root);
            dfs(N+1,i,copy);    
        }
        
    }
    
    void copy1(TreeNode* A,TreeNode* B){
        if(B->left!=NULL){
            A->left=new TreeNode(B->left->val);
            copy1(A->left,B->left);
        }
        if(B->right!=NULL){
            A->right=new TreeNode(B->right->val);
            copy1(A->right,B->right);
        }
        
    }
    
};