package com.fishercoder.solutions;

import com.fishercoder.common.classes.TreeNode;

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

/**
 * 95. Unique Binary Search Trees II
 *
 * 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 static class Solution1 {
		public List<TreeNode> generateTrees(int n) {
			List<TreeNode> result = new ArrayList();
			if (n == 0) {
				return result;
			}
			return generateTrees(1, n);
		}

		private List<TreeNode> generateTrees(int start, int end) {
			List<TreeNode> result = new ArrayList();
			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;
		}
	}
}

@@ -134,429 +134,8 @@
 t;%0A%0A
-/**%0A * 95. Unique Binary Search Trees II%0A *%0A * Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1...n.%0A%0A For example,%0A Given 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
 publ
@@ -150,17 +150,20 @@
  _95 %7B%0A%0A
-%09
+    
 public s
@@ -186,18 +186,24 @@
 tion1 %7B%0A
-%09%09
+        
 public L
@@ -235,27 +235,36 @@
 es(int n) %7B%0A
-%09%09%09
+            
 List%3CTreeNod
@@ -288,27 +288,36 @@
 rrayList();%0A
-%09%09%09
+            
 if (n == 0) 
@@ -322,35 +322,65 @@
 ) %7B%0A
-%09%09%09%09return result;%0A%09%09%09%7D%0A%09%09%09
+                return result;%0A            %7D%0A            
 retu
@@ -403,23 +403,35 @@
 (1, n);%0A
-%09%09%7D%0A%0A%09%09
+        %7D%0A%0A        
 private 
@@ -481,19 +481,28 @@
  end) %7B%0A
-%09%09%09
+            
 List%3CTre
@@ -534,19 +534,28 @@
 List();%0A
-%09%09%09
+            
 if (star
@@ -557,36 +557,48 @@
 (start %3E end) %7B%0A
-%09%09%09%09
+                
 result.add(null)
@@ -603,35 +603,65 @@
 l);%0A
-%09%09%09%09return result;%0A%09%09%09%7D%0A%09%09%09
+                return result;%0A            %7D%0A            
 if (
@@ -676,20 +676,32 @@
  end) %7B%0A
-%09%09%09%09
+                
 result.a
@@ -729,36 +729,66 @@
 ));%0A
-%09%09%09%09return result;%0A%09%09%09%7D%0A%0A%09%09%09
+                return result;%0A            %7D%0A%0A            
 for 
@@ -820,20 +820,32 @@
  i++) %7B%0A
-%09%09%09%09
+                
 List%3CTre
@@ -891,20 +891,32 @@
 i - 1);%0A
-%09%09%09%09
+                
 List%3CTre
@@ -961,20 +961,32 @@
 , end);%0A
-%09%09%09%09
+                
 for (Tre
@@ -1010,21 +1010,36 @@
 List) %7B%0A
-%09%09%09%09%09
+                    
 for (Tre
@@ -1065,22 +1065,40 @@
 List) %7B%0A
-%09%09%09%09%09%09
+                        
 TreeNode
@@ -1126,103 +1126,202 @@
 i);%0A
-%09%09%09%09%09%09root.left = left;%0A%09%09%09%09%09%09root.right = right;%0A%09%09%09%09%09%09result.add(root);%0A%09%09%09%09%09%7D%0A%09%09%09%09%7D%0A%09%09%09%7D%0A%09%09%09
+                        root.left = left;%0A                        root.right = right;%0A                        result.add(root);%0A                    %7D%0A                %7D%0A            %7D%0A            
 retu
@@ -1335,13 +1335,22 @@
 lt;%0A
-%09%09%7D%0A%09
+        %7D%0A    
 %7D%0A%7D%0A

refactor 95