DP solution in C++


  • 0
    H

    using a map to record trees generated with numbers between i and j inclusive.
    for each number in 1 to n choose it as root node, then generate left trees and right trees with a dfs algorithm

    class Solution {public: map<pair<int,int>, vector<TreeNode *> >::iterator it;
    void generateTrees(int b, int e, map<pair<int,int>, vector<TreeNode *> >& dp) 
    {
    	if(b>e)
    	{
    	    return;
    	}
    	it=dp.find(pair<int,int>(b,e));
        if(it!=dp.end())return;
    	vector<TreeNode *>& res=dp[pair<int,int>(b,e)];
    	for(int i=b;i<=e;i++)
    	{
    		generateTrees(b,i-1,dp);
    		generateTrees(i+1,e,dp);
    		if(b>(i-1)&&(i+1)>e)
    		{
    		    TreeNode* tn=new TreeNode(i);
    			res.push_back(tn);
    		}
    		if(b>(i-1))
    		{
    		    vector<TreeNode *>& v2=dp[pair<int,int>(i+1,e)];
    		    for(int k=0;k<v2.size();k++)
    			{
    				TreeNode* tn=new TreeNode(i);
    				tn->right=v2[k];
    				res.push_back(tn);
    			}
    		}
    		if((i+1)>e)
    		{
    		    vector<TreeNode *>& v1=dp[pair<int,int>(b,i-1)];
    		    for(int j=0;j<v1.size();j++)
    			{
    				TreeNode* tn=new TreeNode(i);
    				tn->left=v1[j];
    				res.push_back(tn);
    			}
    		}
    		else
    		{
    		    vector<TreeNode *>& v1=dp[pair<int,int>(b,i-1)];
    		    vector<TreeNode *>& v2=dp[pair<int,int>(i+1,e)];
    		    for(int j=0;j<v1.size();j++)
    			{
    				for(int k=0;k<v2.size();k++)
    				{
    					TreeNode* tn=new TreeNode(i);
    					tn->left=v1[j];
    					tn->right=v2[k];
    					res.push_back(tn);
    				}
    			}
    		}
    	}
    }
    vector<TreeNode *> generateTrees(int n) {
    	vector<TreeNode *> res;
    	map<pair<int,int>, vector<TreeNode *> > dp;
    	if(n==0)
    	{
    	    res.push_back(0);
    	    return res;
    	}
    	generateTrees(1,n,dp);  
    	return dp[pair<int,int>(1,n)];
    }};

  • 0
    H

    Actually I can make the code shorter, however it can't pass the compiler in OJ

    below solution can pass compiler in VS2010

    class Solution {public:	
    map<pair<int,int>, vector<TreeNode *> >::iterator it;
    void generateTrees(int b, int e, map<pair<int,int>, vector<TreeNode *> >& dp) 
    {
    	if(b>e)
    	{
    	    return;
    	}
    	it=dp.find(pair<int,int>(b,e));
        if(it!=dp.end())return;
    	vector<TreeNode *>& res=dp[pair<int,int>(b,e)];
    	for(int i=b;i<=e;i++)
    	{
    		generateTrees(b,i-1,dp);
    		generateTrees(i+1,e,dp);
    		
    		vector<TreeNode *>& v1=b<=(i-1)?dp[pair<int,int>(b,i-1)]:vector<TreeNode *>(1,0);
    		vector<TreeNode *>& v2=(i+1)<=e?dp[pair<int,int>(i+1,e)]:vector<TreeNode *>(1,0);			
    		for(int j=0;j<v1.size();j++)
    		{
    			for(int k=0;k<v2.size();k++)
    			{
    				TreeNode* tn=new TreeNode(i);
    				tn->left=v1[j];
    				tn->right=v2[k];
    				res.push_back(tn);
    			}
    		}
    	}
    }
    vector<TreeNode *> generateTrees(int n) {
    	vector<TreeNode *> res;
    	map<pair<int,int>, vector<TreeNode *> > dp;
    	if(n==0)
    	{
    	    res.push_back(0);
    	    return res;
    	}
    	generateTrees(1,n,dp);  
    	return dp[pair<int,int>(1,n)];
    }};
    

Log in to reply
 

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