题意：Given n, generate all structurally unique BST’s (binary search trees) that store values 1…n. For example, Given n = 3, your program should return all 5 unique BST’s shown below.
13321 \/// \\ 3211 32 //\\ 2123
题解：此题在Unique Binary Search Trees基础上进一步加大了难度，因为要求为BST，则假若生成一颗有i个节点的树，根节点为j+1，，则根节点的左子树节点肯定为[1,j]，而根节点的右子树的节点肯定为[j+2,i]。 我们利用Unique Binary Search Trees中动态规划中的一些技巧，设ans[i]中包含了所有规模为i的不同BST的根节点。
代码如下：
class Solution {public:TreeNode* addVal(TreeNode* now,int add)//将树中的每个节点加上一个固定值add，生成一颗新树{if(now == NULL)return NULL;TreeNode* newNode = new TreeNode((now->val)+add);newNode->left = addVal(now->left,add);newNode->right = addVal(now->right,add);return newNode;}vector<TreeNode *> generateTrees(int n) {vector<vector<TreeNode*> > ans;ans.clear();ans.resize(n+1);ans[0].push_back(NULL);if(n == 0)return ans[0];ans[1].push_back(new TreeNode(1));for(int i = 2;i <= n;i++)//总共有i个节点的BST{for(int j = 0;j < i;j++)//根节点为j+1{for(int k = 0;k < ans[j].size();k++)//根节点的左子树为节点[1,j]{for(int m = 0;m < ans[i-1-j].size();m++)//根节点的右子树为节点[j+2,i]，相当于在子树[1,i-1-j]的每个节点val值加上j+1{TreeNode* newNode = new TreeNode(j+1);newNode->left = ans[j][k];newNode->right = addVal(ans[i-1-j][m],j+1);ans[i].push_back(newNode);}}}}return ans[n];}};
做对的事情比把事情做对重要。
