Unique Binary Search Trees II

题目：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

思路：动态规划

本题目思路是动态规划。

本质上来讲我任选一个节点做根节点，那么我之前的节点都是保存的，我可以直接查表，而之后的dp[i-j]的呢，实际上，只需要把所有后面那部分+j即可。

比如说i=2，j=1,2，假设从1开始 k: 0 – 0 , w: 0 – 0 ,左右各插入一个节点.然后j=2，此时dp[i]又push了2进去。k: 0 – 0 , w: 0 – 0，左边插入一个节点。

也就是说i=2的时候，dp[2]里面保存了前面节点为1 和为2的树。

假如i=1，dp[1]=1；

想一想：dp[2] 有1,2 其中dp[2][0]节点是1，左指向空，右指向2，dp[2][1]节点是2，左指向1，右指向空。

假如i=3，此时存入数字，dp[3]存入1 2 3。对于dp[3][0]来说，存入两个1，一个2，两个3

j=1：k: 0 – 0 , w: 0 – 1；两个1，左边不能放，dp[2]中存在1,2，右边添加节点1+1，和节点2+1.

j=2：k: 0 – 0 , w: 0 – 0；一个2

j=3：k: 0 – 1 , w: 0 – 0；两个3.。。。。。以此类推

每一个dp[i]里面存放了许多的j，而这些j一共有(i-1)*(i-j)个，而这些dp[i]都是指向左右节点。

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution1 {
public:
    vector<TreeNode*> generateTrees(int n) {
        vector<vector<TreeNode *> >dp(n+1);
        if(n<1){
            dp[0].push_back(NULL);
            return dp[0];
        }
        
        dp[0].push_back(NULL);dp[1].push_back(new TreeNode(1));//数字1没有其他节点
        
        for(int i=2;i<=n;i++){
            for(int j=1;j<=i;j++){//单独空的节点不考虑了，所以从1开始
                for(int k=0;k<dp[j-1].size();k++){
                    for(int w=0;w<dp[i-j].size();w++){
                        //dp[i]  push 的次数就是k*w的结果，所以每次都是push i一次
                        //然后他的back的left指向dp[j]的
                        dp[i].push_back(new TreeNode(j));
                        dp[i].back()->left=dp[j-1][k];
                        traverse_add_copy(dp[i-j][w],dp[i].back()->right,j);
                    }
                }
            }
        }
        return dp[n];
    }
  
    void traverse_add_copy(TreeNode *&root,TreeNode *&dst,int val){
        if(root==NULL){
            return;
        }
        dst=new TreeNode(root->val+val);
        if(root->left){
            traverse_add_copy(root->left,dst->left,val);
        }
        if(root->right){
            traverse_add_copy(root->right,dst->right,val);
        }
    }
};


class Solution2 {
public:
    vector<TreeNode*> generateTrees(int n) {
        vector<TreeNode *>result;
        helper(1,n,result);
        return result;
    }
    
    void helper(int start,int end,vector<TreeNode *> &result){
        if(start>end){
            result.push_back(NULL);
            return;//左子树必须小于根节点，所以压入NULL
        }
        
        for(int i=start;i<=end;i++){
            vector<TreeNode *> tmpLeft,tmpRight;
            helper(start,i-1,tmpLeft);
            helper(i+1,end,tmpRight);
            //生成左右子树，从节点start到i-1，还有就是i+1到end
            for(int k=0;k<tmpLeft.size();k++){
                for(int j=0;j<tmpRight.size();j++){
                    TreeNode *root=new TreeNode(i);
                    //本质上是中序遍历
                    root->left=tmpLeft[k];
                    root->right=tmpRight[j];//左边选择比自己小的，右边选择比自己大的
                    result.push_back(root);
                }
            }
        }
    }
};