A simple bottom-up DP solution


  • 9
    A

    The optimal substructure is that for any BST with nodes 1 to n, pick i-th node as root, then the left subtree will contain nodes from 1 to (i-1), and the right subtree will contain nodes from (i+1) to n. I use a 3-d vector to store all possible trees for subtrees with nodes from i to j (0 <= i <= j <=n+1 ), if i==j, there is only one-node tree; if j = i-1, then there is no actual node(storing NULL pointer). Use a bottom up solution to generate all possible subtrees with nodes i to j. Finally the result will be the subtree set with nodes 1 to n,

    	vector<TreeNode *> generateTrees(int n) {
    	if(n == 0)	return vector<TreeNode *>(1, NULL);
    	vector<vector<vector<TreeNode*>>> subtree(n+2, vector<vector<TreeNode*>>(n+2, vector<TreeNode*>()));
    	for(int i=1; i<=n+1; ++i){
    		subtree[i][i].push_back(new TreeNode(i));
    	    subtree[i][i-1].push_back(NULL);	
    	}
    	for(int l=2; l<=n; ++l){
    		for(int i=1; i<=n-l+1; ++i){
    			for(int j=i; j<=i+l-1; ++j){
    				for(int k=0; k<subtree[j+1][i+l-1].size(); ++k){
    				    for(int m=0; m<subtree[i][j-1].size(); ++m){
    				        TreeNode *T = new TreeNode(j);
    				        T->left = subtree[i][j-1][m];
    				        T->right = subtree[j+1][i+l-1][k];
    			            subtree[i][i+l-1].push_back(T);    
    				    }
    				}
    			}
    		}
    	}
    	return subtree[1][n];
    }

Log in to reply
 

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