package com.fishercoder.solutions;

import com.fishercoder.common.classes.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 105. Construct Binary Tree from Preorder and Inorder Traversal
 * Given preorder and inorder traversal of a tree, construct the binary tree.

 Note:
 You may assume that duplicates do not exist in the tree.
 */
public class _105 {

	public static class Solution1 {
		/**
		 * credit: https://discuss.leetcode.com/topic/29838/5ms-java-clean-solution-with-caching use
		 * HashMap as the cache so that accessing inorder index becomes O(1) time Note: The first
		 * element of preorder array is the root!
		 */
		public TreeNode buildTree(int[] preorder, int[] inorder) {
			Map<Integer, Integer> inorderMap = new HashMap();
			for (int i = 0; i < inorder.length; i++) {
				inorderMap.put(inorder[i], i);
			}

			/**At the beginning, both start from 0 to nums.length-1*/
			return buildTree(preorder, 0, preorder.length - 1, inorderMap, 0, inorder.length - 1);
		}

		private TreeNode buildTree(int[] preorder, int preStart, int preEnd,
				Map<Integer, Integer> inorderMap, int inStart, int inEnd) {
			if (preStart > preEnd || inStart > inEnd) {
				return null;
			}

			TreeNode root = new TreeNode(preorder[preStart]);
			int inRoot = inorderMap.get(preorder[preStart]);
			int numsLeft = inRoot - inStart;

			/**It's easy to understand and remember:
			 * for the indices of inorder array:
			 * root.left should be inStart and inRoot-1 as new start and end indices
			 * root.right should be inRoot+1 and inEnd as new start and end indices
			 *
			 * since inRoot is being used already in this recursion call, that's why we use inRoot-1 and inRoot+1
			 * this part is the same for both Leetcode 105 and Leetcode 106.*/
			root.left = buildTree(preorder, preStart + 1, preStart + numsLeft, inorderMap, inStart, inRoot - 1);
			root.right = buildTree(preorder, preStart + numsLeft + 1, preEnd, inorderMap, inRoot + 1, inEnd);
			return root;
		}
	}
}

@@ -131,226 +131,8 @@
 p;%0A%0A
-/**%0A * 105. Construct Binary Tree from Preorder and Inorder Traversal%0A * Given preorder and inorder traversal of a tree, construct the binary tree.%0A%0A Note:%0A You may assume that duplicates do not exist in the tree.%0A */%0A
 publ
@@ -148,17 +148,20 @@
 _105 %7B%0A%0A
-%09
+    
 public s
@@ -188,16 +188,28 @@
 1 %7B%0A
-%09%09/**%0A%09%09
+        /**%0A        
  * c
@@ -297,18 +297,24 @@
 ing use%0A
-%09%09
+        
  * HashM
@@ -395,18 +395,24 @@
 e first%0A
-%09%09
+        
  * eleme
@@ -449,16 +449,28 @@
 ot!%0A
-%09%09 */%0A%09%09
+         */%0A        
 publ
@@ -524,19 +524,28 @@
 rder) %7B%0A
-%09%09%09
+            
 Map%3CInte
@@ -586,19 +586,28 @@
 hMap();%0A
-%09%09%09
+            
 for (int
@@ -641,20 +641,32 @@
  i++) %7B%0A
-%09%09%09%09
+                
 inorderM
@@ -688,25 +688,43 @@
 i%5D, i);%0A
-%09%09%09%7D%0A%0A%09%09%09
+            %7D%0A%0A            
 /**At th
@@ -773,19 +773,28 @@
 gth-1*/%0A
-%09%09%09
+            
 return b
@@ -872,23 +872,35 @@
 h - 1);%0A
-%09%09%7D%0A%0A%09%09
+        %7D%0A%0A        
 private 
@@ -960,20 +960,51 @@
 preEnd,%0A
-%09%09%09%09
+                                   
 Map%3CInte
@@ -1055,19 +1055,28 @@
 nEnd) %7B%0A
-%09%09%09
+            
 if (preS
@@ -1115,34 +1115,64 @@
 ) %7B%0A
-%09%09%09%09return null;%0A%09%09%09%7D%0A%0A%09%09%09
+                return null;%0A            %7D%0A%0A            
 Tree
@@ -1213,27 +1213,36 @@
 preStart%5D);%0A
-%09%09%09
+            
 int inRoot =
@@ -1278,19 +1278,28 @@
 tart%5D);%0A
-%09%09%09
+            
 int nums
@@ -1324,19 +1324,28 @@
 Start;%0A%0A
-%09%09%09
+            
 /**It's 
@@ -1377,19 +1377,28 @@
 member:%0A
-%09%09%09
+            
  * for t
@@ -1426,19 +1426,28 @@
  array:%0A
-%09%09%09
+            
  * root.
@@ -1511,19 +1511,28 @@
 indices%0A
-%09%09%09
+            
  * root.
@@ -1599,17 +1599,35 @@
 ces%0A
-%09%09%09 *%0A%09%09%09
+             *%0A            
  * s
@@ -1724,19 +1724,28 @@
 nRoot+1%0A
-%09%09%09
+            
  * this 
@@ -1803,19 +1803,28 @@
  106.*/%0A
-%09%09%09
+            
 root.lef
@@ -1916,19 +1916,28 @@
 t - 1);%0A
-%09%09%09
+            
 root.rig
@@ -2030,11 +2030,20 @@
 d);%0A
-%09%09%09
+            
 retu
@@ -2055,13 +2055,22 @@
 ot;%0A
-%09%09%7D%0A%09
+        %7D%0A    
 %7D%0A%7D%0A

refactor 105