class Solution {
public:
std::vector<TreeNode*> generateTrees(int n2, int n1=1) {
std::vector<TreeNode*> TreeHeads;
for(int i=n1; i<=n2; ++i) {
auto LeftTrees = i==n1 ? std::vector<TreeNode*>{nullptr} : generateTrees(i1, n1);
auto RightTrees = i==n2 ? std::vector<TreeNode*>{nullptr} : generateTrees(n2, i+1);
for( auto pleft : LeftTrees )
for( auto pright : RightTrees ) {
auto head = new TreeNode(i);
head>left = pleft; head>right = pright;
TreeHeads.push_back(head);
}
}
return TreeHeads;
}
};
Recursive c++ 15 lines


I have the same idea to construct the nnode 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 nnode 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[k1]) { for (auto& R:res[ik]) { 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; }