# C++ solution with recursion, 16ms beats 99.36%

• ``````map<list<int>, vector<TreeNode*>*> M;
vector<TreeNode*>* generateTrees(list<int> & n) {
vector<TreeNode*>* result = new vector<TreeNode*>();

if (n.size() == 0)
{
result->push_back(NULL);
}
else if (n.size() == 1)
{
TreeNode * root = new TreeNode(n.front());
result->push_back(root);
}
else
{
if (M.find(n) != M.end())
{
result = M[n];
}
else
{
for (int i = 0; i < n.size(); i++)
{
list<int> children(n.begin(), n.end());
auto it = children.begin();
int rootEle = *it;
auto next = children.erase(it);

list<int> left(children.begin(), next);
list<int> right(next, children.end());

auto leftTrees = generateTrees(left);
auto rightTrees = generateTrees(right);
for (auto leftIt = leftTrees->begin(); leftIt != leftTrees->end(); leftIt++)
{
for (auto rightIt = rightTrees->begin(); rightIt != rightTrees->end(); rightIt++)
{
TreeNode *root = new TreeNode(rootEle);
root->left = *leftIt;
root->right = *rightIt;
result->push_back(root);
}
}
}
M.emplace(n, result);
}

}

return result;
}

vector<TreeNode*> generateTrees(int n) {
vector<TreeNode*> result;
list<int> list;
fori(n)
{
list.push_back(i+1);
}
if(n != 0)
result = *generateTrees(list);
return result;
}``````

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