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

1 /** 2  * Definition for binary tree 3  * public class TreeNode { 4  *     int val; 5  *     TreeNode left; 6  *     TreeNode right; 7  *     TreeNode(int x) { val = x; left = null; right = null; } 8  * } 9  */10 public class Solution {11     public ArrayList
     
       generateTrees(int n) {12         // Start typing your Java solution below13         // DO NOT write main() function14         return generateTrees(1,n);15     }16     public ArrayList
      
        generateTrees(int a, int b){17         ArrayList
       
         res = new ArrayList
        
         ();18         if(a>b) res.add(null);   19         for(int i=a;i<=b;i++){20             ArrayList
         
           temp1 = generateTrees(a,i-1);21             ArrayList
          
            temp2 = generateTrees(i+1,b);22 for(TreeNode n:temp1)23 for(TreeNode m:temp2){24 TreeNode temp= new TreeNode(i);25 temp.left=n;26 temp.right=m;27 res.add(temp);28 }29 }30 return res;31 }32 }