# My solution based on LeetCode 096 using DP.

• Based on LeetCode 096: Unique Binary Search Trees.

It runs faster without deleteTree.

``````class Solution0 : public Solution {
public:
std::vector<TreeNode*> generateTrees(int n) {
if (!n) return std::vector<TreeNode*>();
std::vector<std::vector<TreeNode*> > trees;
trees.push_back(std::vector<TreeNode*>(1, NULL));
for (int i=1; i<=n; ++i) {    // Dynamic programming.
std::vector<TreeNode*> next_trees;
for (int j=1; j<=i; ++j) {  // Everyone can be the root.
for (int k=0; k<trees[j-1].size(); ++k) // There're k nodes in left subtree.
for (int l=0; l<trees[i-j].size(); ++l) {
TreeNode * root = new TreeNode(j);
root->left = copyTree(trees[j-1][k]);
root->right = copyTree(trees[i-j][l], j);
next_trees.push_back(root);
}
}
trees.push_back(next_trees);
}
for (int i=1; i<trees.size()-1; ++i)
for (int j=0; j<trees[i].size(); ++j)
deleteTree(trees[i][j]);
return trees.back();
}
private:
TreeNode * copyTree(TreeNode * root, int offset = 0) {
if (!root) return root;
TreeNode * new_root = new TreeNode(root->val + offset);
new_root->left = copyTree(root->left, offset);
new_root->right = copyTree(root->right, offset);
return new_root;
}
void deleteTree(TreeNode * tn) {
if (!tn) return;
deleteTree(tn->left);
deleteTree(tn->right);
delete tn;
}
};``````

• why this is a DP solution? I don't think this solution reflect something like DP.

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