# Recursive c++ 15 lines

• ``````class Solution {
public:
std::vector<TreeNode*> generateTrees(int n2, int n1=1) {
for(int i=n1; i<=n2; ++i) {
auto LeftTrees = i==n1 ? std::vector<TreeNode*>{nullptr} : generateTrees(i-1, n1);
auto RightTrees = i==n2 ? std::vector<TreeNode*>{nullptr} : generateTrees(n2, i+1);
for( auto pleft : LeftTrees )
for( auto pright : RightTrees ) {
}
}
}
};

``````

• I have the same idea to construct the n-node tree using previous smaller trees as left and right subtrees. However, I used DP and a helper function to make deep copy with node value shifted, I feel it has be to redundant and uses too much space to store all trees of less than n nodes even though we only need n-node trees. Thanks for sharing the solution.

I attached my code below.

``````    vector<TreeNode*> generateTrees(int n) {
if (n <= 0) return {};
// DP to store the results from 1 node and n nodes (which uses too much space)
vector<vector<TreeNode*>> res(n+1);
res[0] = { NULL };
for (int i = 1; i <= n; i++) {
for (int k = 1; k <= i; k++) {
for (auto& L:res[k-1]) {
for (auto& R:res[i-k]) {
TreeNode* r = new TreeNode(k);
r->left = deppCopyShift(L, 0);
r->right = deppCopyShift(R, k);
res[i].push_back(r);
}
}

}
}
return res[n];
}

TreeNode* deppCopyShift(TreeNode* r, int x) {
TreeNode* copy_r = NULL;
if (!r) return copy_r;

copy_r = new TreeNode(r->val+x);
copy_r->left = deppCopyShift(r->left, x);
copy_r->right = deppCopyShift(r->right, x);
return copy_r;
}

``````

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