题目：

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来分别接收左右子树。

 

代码：

1     public  List
     
       generateTrees(int n){ 2         return generateTrees(1, n); 3     } 4      5     public List
      
        generateTrees(int begin, int end){ 6         List
       
         arr = new ArrayList
        
         (); 7         if(begin > end){ 8             return arr; 9         }10         if(begin == end){11             TreeNode ptr = new TreeNode(begin);12             arr.add(ptr);13             return arr;14         }15         for(int i = begin; i <= end; i++){16             List
         
           left = new ArrayList
          
           ();17 List
           
             right = new ArrayList
            
             ();18 left = generateTrees(begin, i-1);19 right = generateTrees(i+1, end);20 //注意判断left和right是否为空21 //还有，要注意应该在最内层循环每次都新建根结点22 if(left.size() == 0){ 23 if(right.size() == 0){24 TreeNode root = new TreeNode(i);25 root.left = null;26 root.right = null;27 arr.add(root);28 }else{29 for(TreeNode r: right){30 TreeNode ptr = new TreeNode(i);31 ptr.left = null;32 ptr.right = r;33 arr.add(ptr);34 }35 }36 }else{37 if(right.size() == 0){38 for(TreeNode l: left){39 TreeNode ptr = new TreeNode(i);40 ptr.left = l;41 ptr.right = null;42 arr.add(ptr);43 }44 }else{45 for(TreeNode l: left){46 for(TreeNode r: right){47 TreeNode ptr = new TreeNode(i);48 ptr.left = l;49 ptr.right = r;50 arr.add(ptr);51 }52 }53 }54 }55 }56 return arr;57 }