package com.fishercoder.solutions;

import com.fishercoder.common.classes.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**Given an integer 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*/
public class _95 {

	public List<TreeNode> generateTrees_pure_recursion(int n) {
		List<TreeNode> result = new ArrayList<TreeNode>();
		if (n == 0) {
			return result;
		}
		return generateTrees(1, n);
	}

	private List<TreeNode> generateTrees(int start, int end) {
		List<TreeNode> result = new ArrayList<TreeNode>();
		if (start > end) {
			result.add(null);
			return result;
		}
		if (start == end) {
			result.add(new TreeNode(start));
			return result;
		}

		for (int i = start; i <= end; i++) {
			List<TreeNode> leftList = generateTrees(start, i - 1);
			List<TreeNode> rightList = generateTrees(i + 1, end);
			for (TreeNode left : leftList) {
				for (TreeNode right : rightList) {
					TreeNode root = new TreeNode(i);
					root.left = left;
					root.right = right;
					result.add(root);
				}
			}
		}
		return result;
	}
}

@@ -133,16 +133,60 @@
 st;%0A%0A/**
+%0A * 95. Unique Binary Search Trees II%0A *%0A * 
 Given an
@@ -569,16 +569,50 @@
  _95 %7B%0A%0A
+%09public static class Solution1 %7B%0A%09
 %09public 
@@ -643,23 +643,8 @@
 rees
-_pure_recursion
 (int
@@ -645,24 +645,25 @@
 es(int n) %7B%0A
+%09
 %09%09List%3CTreeN
@@ -685,38 +685,29 @@
 ew ArrayList
-%3CTreeNode%3E
 ();%0A
+%09
 %09%09if (n == 0
@@ -709,24 +709,25 @@
  == 0) %7B%0A%09%09%09
+%09
 return resul
@@ -731,18 +731,20 @@
 sult;%0A%09%09
+%09
 %7D%0A
+%09
 %09%09return
@@ -765,20 +765,22 @@
 (1, n);%0A
+%09
 %09%7D%0A%0A
+%09
 %09private
@@ -833,16 +833,17 @@
 nd) %7B%0A%09%09
+%09
 List%3CTre
@@ -875,24 +875,15 @@
 List
-%3CTreeNode%3E
 ();%0A%09%09
+%09
 if (
@@ -889,32 +889,33 @@
 (start %3E end) %7B%0A
+%09
 %09%09%09result.add(nu
@@ -918,24 +918,25 @@
 d(null);%0A%09%09%09
+%09
 return resul
@@ -938,22 +938,24 @@
 result;%0A
+%09
 %09%09%7D%0A%09%09
+%09
 if (star
@@ -966,16 +966,17 @@
  end) %7B%0A
+%09
 %09%09%09resul
@@ -1003,16 +1003,17 @@
 tart));%0A
+%09
 %09%09%09retur
@@ -1024,19 +1024,21 @@
 sult;%0A%09%09
+%09
 %7D%0A%0A
+%09
 %09%09for (i
@@ -1064,24 +1064,25 @@
 end; i++) %7B%0A
+%09
 %09%09%09List%3CTree
@@ -1126,24 +1126,25 @@
  i - 1);%0A%09%09%09
+%09
 List%3CTreeNod
@@ -1184,24 +1184,25 @@
 1, end);%0A%09%09%09
+%09
 for (TreeNod
@@ -1218,24 +1218,25 @@
 leftList) %7B%0A
+%09
 %09%09%09%09for (Tre
@@ -1267,16 +1267,17 @@
  %7B%0A%09%09%09%09%09
+%09
 TreeNode
@@ -1302,24 +1302,25 @@
 de(i);%0A%09%09%09%09%09
+%09
 root.left = 
@@ -1325,16 +1325,17 @@
 = left;%0A
+%09
 %09%09%09%09%09roo
@@ -1352,24 +1352,25 @@
 right;%0A%09%09%09%09%09
+%09
 result.add(r
@@ -1383,19 +1383,23 @@
 %09%09%09%09
+%09
 %7D%0A
+%09
 %09%09%09%7D%0A%09%09
+%09
 %7D%0A
+%09
 %09%09re
@@ -1411,13 +1411,17 @@
 result;%0A
+%09%09%7D%0A
 %09%7D%0A%7D%0A

refactor 95