Unique Binary Search Trees II @LeetCode

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.

	package leetcode.tree;
	import java.util.ArrayList;
	/**
	* Solution: 跟Unique BST I 思路一样，划分左右子树，递归构造，然后拼接.必须先理解I。
	* result.add(null) 很重要，返回后需要null值来构造，否则ArrayList 为null
	* 每次划分root 为i, 构造 (start, i-1) 和 (i+1,end) 的部分, 记住构造时候是双重循环.
	*
	* Reference: http://fisherlei.blogspot.com/2013/03/leetcode-unique-binary-search-trees-ii.html
	* @author jeffwan
	* @date Apr 14, 2014
	*/
	public class GenerateTrees {
	public ArrayList<TreeNode> generateTrees(int n) {
	return generate(1, n);
	}
	private ArrayList<TreeNode> generate(int start, int end) {
	ArrayList<TreeNode> result = new ArrayList<TreeNode>();
	if (start > end) {
	result.add(null);
	return result;
	}
	for (int i = start; i <= end; i++) {
	ArrayList<TreeNode> leftTree = generate(start, i - 1);
	ArrayList<TreeNode> rightTree = generate(i + 1, end);
	for (TreeNode left : leftTree) {
	for (TreeNode right : rightTree) {
	TreeNode root = new TreeNode(i);
	root.left = left;
	root.right = right;
	result.add(root);
	}
	}
	}
	return result;
	}
	// TreeNode
	private class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode (int x) {
	val = x;
	}
	}
	}

view raw GenerateTrees.java hosted with ❤ by GitHub