95. Unique Binary Search Trees II Leetcode Java

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

Solution:

Besides to know how many unique binary trees are there, this problem require to list all possible BSTs. 

The basic idea is the same, construct every possible BST by picking the root from 1 to n, and eg. if we pick i as the root, then the left child will be construct all possible BSTs for n=i-1, while right child will be construct all BSTs for i+1-> n. So we can have a helper method which will construct all BSTs with a starting number and an ending number. Then for root i, we call this helper(1,i-1) to get a list of all possible BSTs as root i's left, and helper(i+1,n) to get all possible BSTs as root i's right. Assume there are m possible left BSTs and n possible right BSTs, the total number of possible BSTs rooted with i will be m*n. 

 public List<TreeNode> generateTrees(int n) {  
     return helper(1,n);   
   }  
   public List<TreeNode> helper(int start, int end){  
     if(start>end){  
       List<TreeNode> res=new ArrayList<TreeNode>();  
       res.add(null);  
       return res;  
     }  
     List<TreeNode> res=new ArrayList<TreeNode>();  
     for(int i=start;i<=end;i++){  
       List<TreeNode> left=helper(start,i-1);  
       List<TreeNode> right=helper(i+1,end);  
       for(int j=0;j<left.size();j++){  
         for(int k=0;k<right.size();k++){  
           TreeNode root=new TreeNode(i);  
           root.left=left.get(j);  
           root.right=right.get(k);  
           res.add(root);  
         }  
       }  
     }  
    return res;  
   }