@@ -0,0 +1,2119 @@
+/**%0A *%09Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.%0A *%0A *%09For example,%0A *%09Given n = 3, your program should return all 5 unique BST's shown below.%0A *%0A *  1         3     3      2      1%0A *   %5C       /     /      / %5C      %5C%0A *    3     2     1      1   3      2%0A *   /     /       %5C                 %5C%0A *  2     1         2                 3%0A *%0A *%09Author: matao%0A *%0A */%0A%0Aimport java.util.List;%0Aimport java.util.ArrayList;%0A%0Aclass TreeNode %7B%0A%09int val;%0A%09TreeNode left;%0A%09TreeNode right;%0A%09TreeNode(int x) %7B %0A%09%09val = x; %0A%09%7D%0A%7D%0A%0Apublic class UniqueBinarySearchTreesII %7B%0A%09public static List%3CTreeNode%3E generateTrees(int n) %7B%0A%09%09return generate(1, n);%0A    %7D%0A%0A    public static List%3CTreeNode%3E generate(int start, int end) %7B%0A    %09List%3CTreeNode%3E result = new ArrayList%3CTreeNode%3E();%0A    %09if(start %3E end) %7B%0A    %09%09result.add(null);%0A    %09%09return result;%0A    %09%7D%0A%0A    %09for (int i = start; i %3C= end; i++) %7B%0A    %09%09List%3CTreeNode%3E left = generate(start, i-1);%0A    %09%09List%3CTreeNode%3E right = generate(i+1, end);%0A    %09%09for (TreeNode l : left) %7B%0A    %09%09%09for (TreeNode r : right) %7B%0A    %09%09%09%09TreeNode root = new TreeNode(i);%0A    %09%09%09%09root.left = l;%0A    %09%09%09%09root.right = r;%0A    %09%09%09%09result.add(root);%0A    %09%09%09%7D%0A    %09%09%7D%0A    %09%7D%0A    %09return result;%0A    %7D%0A%0A    public static void InOrderTraverse(TreeNode root) %7B%0A    %09if (root == null) %7B%0A    %09%09return;%0A    %09%7D%0A    %09System.out.print(root.val + %22 %22);%0A    %09InOrderTraverse(root.left);%0A    %09InOrderTraverse(root.right);%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A    %09List%3CTreeNode%3E roots0 = generateTrees(0);%0A    %09for (TreeNode root : roots0) %7B%0A    %09%09InOrderTraverse(root);%0A    %09%09System.out.println();%0A    %09%7D%0A%0A    %09List%3CTreeNode%3E roots1 = generateTrees(1);%0A    %09for (TreeNode root : roots1) %7B%0A    %09%09InOrderTraverse(root);%0A    %09%09System.out.println();%0A    %09%7D%0A%0A    %09List%3CTreeNode%3E roots2 = generateTrees(2);%0A    %09for (TreeNode root : roots2) %7B%0A    %09%09InOrderTraverse(root);%0A    %09%09System.out.println();%0A    %09%7D%0A%0A    %09List%3CTreeNode%3E roots3 = generateTrees(3);%0A    %09for (TreeNode root : roots3) %7B%0A    %09%09InOrderTraverse(root);%0A    %09%09System.out.println();%0A    %09%7D%0A    %7D%0A%7D

add Unique Binary Search Trees II solution