16 ms C++ DP solution


  • 0
    C
    vector<TreeNode*> generateTrees(int n) {
        if(n > 0){
            vector<vector<vector<TreeNode*> > > dp(n + 2,vector<vector<TreeNode*> > (n + 2, vector<TreeNode*>(1,NULL)));
            
            for(int diff = 0,end = n;diff <= n;diff ++,end--){
                for(int base = 1;base <= end;base++){
                    int lower = base;
                    int upper = base + diff;
                    
                    vector<TreeNode*> itemNodes;
                    for(int root = lower;root <= upper;root++){
                        vector<TreeNode*> nodes;
                        for(TreeNode* leftChild : dp[lower][root - 1]){
                            for(TreeNode* rightChild : dp[root + 1][upper]){
                                TreeNode* rootNode = new TreeNode(root);
                                rootNode -> left = leftChild;
                                rootNode -> right = rightChild;
                                nodes.push_back(rootNode);
                            }
                        }
                        itemNodes.insert(itemNodes.end(),nodes.begin(),nodes.end());
                    }
                    dp[lower][upper] = itemNodes;
                }
                
            }
            return dp[1][n];
        }
        return vector<TreeNode*>{};
    }

Log in to reply
 

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