Sharing my 24ms C++ solution


  • 0
    T
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    private:
        vector<TreeNode*> generateTreesHelper(int left, int right)
        {
            vector<TreeNode*> result;
            if(left>right)
            {
                result.push_back(NULL);
                return result;
            }
    
            else
            {
                int i, k, l;
                for(i=left; i<=right; i++)
                {
                    vector<TreeNode*> lresult = generateTreesHelper(left, i-1);
                    vector<TreeNode*> rresult = generateTreesHelper(i+1, right);
                    for(k=0; k<lresult.size(); k++)
                        for(l=0; l<rresult.size(); l++)
                            {
                                TreeNode* tree = new TreeNode(i);
                                tree->left  = lresult[k];
                                tree->right = rresult[l];
                                result.push_back(tree);
                            }
                }
                return result;
            }
        }
    public:
        vector<TreeNode*> generateTrees(int n) {
            vector<TreeNode*> result;
            if(n==0)
                return result;
            return generateTreesHelper(1, n);
        }
    };

Log in to reply
 

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