My c++ novelty idea ,28ms。use DP

• The basic idea is we can get the result of n node tree form result of 0 node tree to n-1 node tree.
We use dp[i] to save the result of i node tree.
Given a sequence 1…i, we pick a number j out of the sequence as the root.
then, root->left = dp[j - 1]; root->right = dp[i - j] +j

My english is not good , so , read the code.
By the way , the code may cause memory leak.

``````class Solution {
public:
vector<TreeNode*> generateTrees(int n) {
vector<vector<TreeNode*>> dp(n + 1);
if (n < 1) {
dp[0].push_back(NULL);
return dp[0];
}
dp[0].push_back(NULL); dp[1].push_back(new TreeNode(1));
for (int i = 2; i < n + 1; i++) {
for (int j = 1; j <= i; j++)
for (int k = 0; k < dp[j - 1].size(); k++)
for (int w = 0; w < dp[i-j].size(); w++)
{
dp[i].push_back(new TreeNode(j));
dp[i].back()->left = dp[j-1][k];
traverse_add_copy(dp[i - j][w], &dp[i].back()->right, j);
}
}
return dp[n];
}
private:
void traverse_add_copy(TreeNode* root, TreeNode **dst, int val)
{
if (root == NULL) return;
*dst = new TreeNode(root->val + val);
if (root->left)
traverse_add_copy(root->left, &(*dst)->left, val);
if (root->right)
traverse_add_copy(root->right, &(*dst)->right, val);
}
};``````

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