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

confused what "{1,#,2,3}" means? 

题解：这道题比1难的就是不是返回个数，而是返回全部结果。从http://blog.csdn.net/sinat_24520925/article/details/45562273可知可行的二叉查找树的数量时对应的卡特兰数。由于左右子数也是一棵树，仅仅是树节点的值不同，所以我们用递归的方法求全部树的结构。分成左子树以及右子树，将1~n先分成两部分，之后将这两部分递归所组成子树挂在根节点下就可以，代码例如以下：

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:    vector
     
      subTree(int start,int end)    {        vector
      
        res;        if(start>end)        {            res.push_back(NULL);            return res;        }        for(int k=start;k<=end;k++)        {            vector
       
         left=subTree(start,k-1);            vector
        
          right=subTree(k+1,end);            for(int i=0;i
         
          left=left[i];                    node->right=right[j];                    res.push_back(node);                }            }        }        return res;            }    vector
          
            generateTrees(int n) { vector
           
             res; res=subTree(1,n); return res; }};