这题首先要明白的是，二叉搜索树的左子树和右子树都自成二叉搜索树。这种递归定义决定了，如果我知道从1到n - 1时，所有的二叉搜索树结构，那结点数为n的二叉搜索树也可以得到了。
转换关系是这样的：
对于一个含有n个结点的二叉搜索树，首先树根可以从i = 1~n变化，然后左右子树的结点数目分别是i - 1和 n- i。
这样分析下来，动态规划的思路就比较明显了。这题麻烦点的是对于一颗树的复制.
TreeNode *copyTree(TreeNode *root, int offSet){
if (root == nullptr)
return nullptr;
TreeNode *nRoot = new TreeNode(root->val + offSet);
nRoot->left = copyTree(root->left, offSet);
nRoot->right = copyTree(root->right, offSet);
return nRoot;
}
vector<TreeNode *> generateTrees(int n) {
vector<TreeNode *> result;
if (n == 0){
result.push_back(nullptr);
return result;
}
vector<vector<TreeNode*> > table(n + 1);
TreeNode *t1 = new TreeNode(1);
table[0] = {nullptr};
table[1] = {t1};
for (int i = 2; i < n + 1; i++){
vector<TreeNode*> row;
for (int j = 1; j < i + 1; j++){
//vector<TreeNode*> lt = table[j - 1];//left: no offset
//vector<TreeNode*> rt = table[i - j];//right: offset by j
for (auto lIt = table[j - 1].begin();
lIt != table[j - 1].end(); lIt++){
for (auto rIt = table[i - j].begin(); rIt != table[i - j].end();
rIt++){
TreeNode *midNode = new TreeNode(j);
midNode->left = copyTree(*lIt, 0);
midNode->right = copyTree(*rIt, j);
row.push_back(midNode);
}
}
}
table[i] = row;
}
return table[n];
}