Leetcode: Unique Binary Search Trees II

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

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Understand the problem:
The main difference between the BST I is it requires to output all unique BSTs. So we can use recursion solution.


Solution:

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

/**  * Definition for binary tree  * public class TreeNode {  *     int val;  *     TreeNode left;  *     TreeNode right;  *     TreeNode(int x) { val = x; left = null; right = null; }  * }  */ public class Solution {     public List<TreeNode> generateTrees(int n) {         return generateTreesHelper(1, n);     }           private List<TreeNode> generateTreesHelper(int start, int end) {         List<TreeNode> result = new ArrayList<TreeNode>();                   if (start > end) {             result.add(null);             return result;         }                   for (int i = start; i <= end; i++) {             List<TreeNode> left = generateTreesHelper(start, i - 1);             List<TreeNode> right = generateTreesHelper(i + 1, end);                           for (TreeNode l : left) {                 for (TreeNode r : right) {                     TreeNode root = new TreeNode(i);                     root.left = l;                     root.right = r;                     result.add(root);                 }             }         }                   return result;     } }