DP using C++(20ms)


  • 0
    B
    class Solution {
    public:
    vector<vector<vector<TreeNode*> > > dp;
    vector<vector<bool> > test;
    
    vector<TreeNode*> search(int left, int right){
        vector<TreeNode* > vec;
        if(left > right){
            vec.push_back(NULL);
            return vec;
        } 
        
        if(test[left][right]) return dp[left][right];
        
        for(int i = left; i <= right; i ++){
            vector<TreeNode *> ltree = search(left, i - 1);
            vector<TreeNode *> rtree = search(i + 1, right);
            
            for(int j = 0; j < ltree.size(); j ++){
                for(int k = 0; k < rtree.size(); k ++){
                    TreeNode* root = new TreeNode(i);
                    root->left = ltree[j];
                    root->right = rtree[k];
                    vec.push_back(root);
                }
            }
        }
        
        dp[left][right] = vec;
        test[left][right] = true;
        return vec;
    }
    
    vector<TreeNode*> generateTrees(int n) {
    	for(int i = 0; i <= n; i ++){
            vector<bool> v(n + 1, false);
            test.push_back(v);
    
    		vector<vector<TreeNode*> > vv(n + 1, vector<TreeNode*>(n+1, NULL));
            dp.push_back(vv);
        }
        
        return search(1, n);
    }
    

    };


Log in to reply
 

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