题目：
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.
思路：
本题采取递归的思路。
传递的参数是开始数值(begin)和结束数值(end)。
当begin > end 时，返回空(注意不是null)；
当begin == end 时， 返回含有 new TreeNode(begin)结点的ArrayList；
当begin < end时，建立两个ArrayList来分别接收左右子树。
代码：
public List<TreeNode> generateTrees(int n){
return generateTrees(1, n);
}
public List<TreeNode> generateTrees(int begin, int end){
List<TreeNode> arr = new ArrayList<TreeNode>();
if(begin > end){
return arr;
}
if(begin == end){
TreeNode ptr = new TreeNode(begin);
arr.add(ptr);
return arr;
}
for(int i = begin; i <= end; i++){
List<TreeNode> left = new ArrayList<TreeNode>();
List<TreeNode> right = new ArrayList<TreeNode>();
left = generateTrees(begin, i-1);
right = generateTrees(i+1, end);
//注意判断left和right是否为空
//还有，要注意应该在最内层循环每次都新建根结点
if(left.size() == 0){
if(right.size() == 0){
TreeNode root = new TreeNode(i);
root.left = null;
root.right = null;
arr.add(root);
}else{
for(TreeNode r: right){
TreeNode ptr = new TreeNode(i);
ptr.left = null;
ptr.right = r;
arr.add(ptr);
}
}
}else{
if(right.size() == 0){
for(TreeNode l: left){
TreeNode ptr = new TreeNode(i);
ptr.left = l;
ptr.right = null;
arr.add(ptr);
}
}else{
for(TreeNode l: left){
for(TreeNode r: right){
TreeNode ptr = new TreeNode(i);
ptr.left = l;
ptr.right = r;
arr.add(ptr);
}
}
}
}
}
return arr;
}