C++ Solution for Unique Binary Search Trees 2


  • 0
    G
    class Solution {
    public:
        vector<TreeNode*> generateTrees(int n) {
            vector<vector<TreeNode*>> result(n+1,vector<TreeNode*>());
            if(n==0)return result[0];
    
            TreeNode* node = new TreeNode(1);
            vector<TreeNode*> vec(1,node);
            result[1]=vec;
            if(n==1)return result[1];
            
            for(int i=2;i<n+1;i++)
                for(int j=1;j<=i;j++)
                    newTree(i,j,result);
            return result[n];
        }
        
        void newTree(int num,int LEFT,vector<vector<TreeNode*>> &result){
            // TreeNode* newNode=new TreeNode(LEFT);
            if(LEFT-1==0){
                for(int j=0;j<result[num-LEFT].size();j++){
                    TreeNode* newNode=new TreeNode(LEFT);
                    newNode->left=NULL;
                    TreeNode* tree=clone(result[num-LEFT][j],LEFT);
                    newNode->right=tree;
                    result[num].push_back(newNode);
                }return;
            }
            if(num-LEFT==0){
                for(int i=0;i<result[LEFT-1].size();i++){
                    TreeNode* newNode=new TreeNode(LEFT);
                    newNode->right=NULL;
                    newNode->left=clone(result[LEFT-1][i],0);
                    result[num].push_back(newNode);
                }return;
            }
    
            for(int i=0;i<result[LEFT-1].size();i++){
                for(int j=0;j<result[num-LEFT].size();j++){
                    TreeNode* newNode=new TreeNode(LEFT);
                    newNode->left=(result[LEFT-1][i]);
                    TreeNode* tree=clone(result[num-LEFT][j],LEFT);
                    newNode->right=tree;
                    result[num].push_back(newNode);
                }
            }
        }
        
        TreeNode* clone(TreeNode* root,int num){
            if(root==NULL)return root;
            TreeNode* root1=new TreeNode(root->val+num);
            root1->left=clone(root->left,num);
            root1->right=clone(root->right,num);
            return root1;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.