Leetcode 95 Solution

/**
 * 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 {
public:
    vector<TreeNode*> generateTrees(int l, int r)
    {
        vector<TreeNode*> res;

        if (l == r)
        {
            TreeNode* node = new TreeNode(l);
            res.push_back(node);
            return res;
        }

        for (int i = l; i <= r; i++)
        {
            vector<TreeNode*> left_trees;
            vector<TreeNode*> right_trees;

            if (i == l)
                left_trees.push_back(NULL);
            else
                left_trees = generateTrees(l, i - 1);

            if (i == r)
                right_trees.push_back(NULL);
            else
                right_trees = generateTrees(i + 1, r);

            for (auto it1 = left_trees.begin(); it1 != left_trees.end(); it1++)
            {
                for (auto it2 = right_trees.begin(); it2 != right_trees.end(); it2++)
                {
                    TreeNode* root = new TreeNode(i);
                    root->left = *it1;
                    root->right = *it2;

                    res.push_back(root);
                }
            }
        }

        return res;
    }

    vector<TreeNode*> generateTrees(int n) {
        return generateTrees(1, n);
    }
};