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.

Solution : Divide and Conquer

from 1-> n, for each point calculate left side trees and right side trees and then construct them together. 

	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
	/**
	* 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 ArrayList<TreeNode> generateTrees(int n) {
	// Start typing your Java solution below
	// DO NOT write main() function
	ArrayList<TreeNode> result=generateBST(1,n);
	return result;
	}
	public ArrayList<TreeNode> generateBST(int start, int end){
	ArrayList<TreeNode> subTree=new ArrayList<TreeNode>();
	if (start>end){
	subTree.add(null);
	}
	else if (start==end){
	subTree.add(new TreeNode(start));
	}
	else{
	for (int i=start; i<=end; i++){
	// divied and conquer.
	// get collection of all left trees and right trees
	// then construct them together
	ArrayList<TreeNode> leftTree=generateBST(start, i-1);
	ArrayList<TreeNode> rightTree=generateBST(i+1, end);
	for (TreeNode leftNode:leftTree){
	for(TreeNode rightNode:rightTree){
	TreeNode root=new TreeNode(i);
	root.left=leftNode;
	root.right=rightNode;
	subTree.add(root);
	}
	}
	}
	}
	return subTree;
	}
	}

view raw Unique Binary Search Trees II.java hosted with ❤ by GitHub