LeetCode--Unique Binary Search Trees II(DP求BST)

题意：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.

1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3

题解：此题在Unique Binary Search Trees基础上进一步加大了难度，因为要求为BST，则假若生成一颗有i个节点的树，根节点为j+1，则根节点的左子树节点肯定为[1,j]，而根节点的右子树的节点肯定为[j+2,i]。
我们利用Unique Binary Search Trees中动态规划中的一些技巧，设ans[i]中包含了所有规模为i的不同BST的根节点。

1. 对于规模为i的BST，我们枚举它所有可能的根节点[1,i]。
2. 若根节点为j+1，由上面的分析可知我们已经知道了左子树即规模为j的所有BST：ans[j]，则直接枚举将它接在根节点的左子树即可。
3. 而右子树规模为i-1-j，但是其节点上的key值应该为[j+2,i]，所以我们不能直接枚举ans[i-1-j]的所有根节点将它接在右子树上，我们需要生成一颗新的规模为i-1-j的子树，并且将它的所有key值加上j+1。

代码如下：

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];
    }
};