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

Question

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;     
    }
};

Answer 1

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;     
    }
};

Comments

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?

Answer 2

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