Tuesday, October 7, 2014

Unique Binary Search Trees II

class Solution {
public:
    vector<TreeNode *> generateTrees(int n) {
        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;    
    }
};

No comments:

Post a Comment