unique binary search trees. Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.
vector<treenode*> generate_unique_trees(int n) {
vector<treenode*> res;
dfs(res, 1, n);
return res;
}
void dfs(vector<treenode*> &res, int low, int high) {
if(low > high) {
res.push_back(NULL);
return;
}
for(int i=low; i<high; i++) {
vector<treenode*> left_trees, right_trees;
dfs(left_trees, low, i-1);
dfs(right_trees, i+1, high);
// POS1
for(int j=0; j<left_trees.size(); j++) {
for(int k=0; k<right_trees.size(); k++) {
treenode *root = new treenode(i); // gist, should be here, not at POS1
root->left = left_trees[j];
root->right = right_trees[k];
res.push_back(root);
}
}
}
}