[Run time error]: same code does not have problem with VS9


  • 0
    W

    I got a run time error when input is "1".
    Here is the code:

    class Solution {
    public:
        vector<TreeNode *> generateTrees(int n) {
            // IMPORTANT: Please reset any member data you declared, as
            // the same Solution instance will be reused for each test case.
    		return helper(1,n);
        }
    private:
    	vector<TreeNode *> helper(int start, int end){
    	vector <TreeNode*> results;
    	if(start>end)	
    	{
    		results.push_back(NULL); 
    		return results;
    	}
    	for(int i=start; i<=end; ++i)
    	{
    		vector <TreeNode*> left=helper(start,i-1); //already includes NULL vector
    		vector <TreeNode*> right=helper(i+1,end); //already includes NULL vector
    		TreeNode root(i);
    		for(int j=0; j<left.size(); ++j)
    		{
    			for(int k=0; k<right.size(); ++k)
    			{
    				root.left=left[j];
    				root.right=right[k];
    				results.push_back(&root);
    			}
    		}
    	}
    	return results;		
    	}
    };

  • 8
    P

    Hey, you are pushing a pointer to a local variable to the vector and this is dangerous because the local variable will be destroyed after you return the vector.

    To be specific, the following code will not work properly.

    results.push_back(&root);
    

    You have to create the TreeNode dynamically.

    class Solution {
    public:
        vector<TreeNode *> generateTrees(int n) {
            // IMPORTANT: Please reset any member data you declared, as
            // the same Solution instance will be reused for each test case.
            return helper(1,n);
        }
    private:
        vector<TreeNode *> helper(int start, int end){
        vector <TreeNode*> results;
        if(start>end)   
        {
            results.push_back(NULL); 
            return results;
        }
        for(int i=start; i<=end; ++i)
        {
            vector <TreeNode*> left=helper(start,i-1); //already includes NULL vector
            vector <TreeNode*> right=helper(i+1,end); //already includes NULL vector
            TreeNode* root;
            for(int j=0; j<left.size(); ++j)
            {
                for(int k=0; k<right.size(); ++k)
                {
                    root = new TreeNode(i);
                    root->left=left[j];
                    root->right=right[k];
                    results.push_back(root);
                }
            }
        }
        return results;     
        }
    };

  • 0

    Except local variable mentioned below, root should be created inside two for loop, otherwise senseless.


  • 0

    This code will generate a list of trees that interleave with each other, does it? To my intuition an elegant solution should generate a list of trees that are isolated with each other. My idea is to generate a preorder sequence and use the algorithm of "Construct Binary Tree from Preorder and Inorder Traversal" to construct a independent tree, but the code will be much longer. Is there any elegant and short solution that can construct separate trees?


  • 0
    Z

    Will the recursive solution generate many sub-tress repeatedly? Is it possible to use DP based solution?


  • 0
    P

    I think DP is fine.


Log in to reply
 

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