C++ beats 96%, half deep copy and half shallow copy, so save a lot of time


  • 0
    I

    '''

    vector<vector<TreeNode*>> dp;
    vector<TreeNode*> generateTrees(int n) {
        dp=vector<vector<TreeNode*>>(n+1,vector<TreeNode*>());
        if (n==0) return vector<TreeNode*>();
        return gt(n);
    
    }
    vector<TreeNode*> gt(int n) {
        if (dp[n].size()>0) return dp[n];
        if (n==0) return dp[n]=vector<TreeNode*>(1,NULL);
        vector<TreeNode*> res;
        for (int i=0;i<n;i++){
            vector<TreeNode*> left=gt(i);
            vector<TreeNode*> right=gt(n-1-i);
            for (TreeNode* l:left){
                for (TreeNode* r:right){
                    TreeNode* root=new TreeNode(i+1);
                    root->left=l;  //shallow copy
                    root->right=sub(r,i+1);  //deep copy
                    res.push_back(root);
                }
            }
        }
        return dp[n]=res;
    
    }
    TreeNode* sub(TreeNode* r,int b){  //deep copy
        if (r==NULL) return NULL;
        TreeNode* root=new TreeNode(r->val+b);
        root->left=sub(r->left,b);
        root->right=sub(r->right,b);
        return root;
    }
    

    '''


Log in to reply
 

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