package com.fishercoder.solutions;

import com.fishercoder.common.classes.TreeNode;

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

/**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 {

	/**
	 * 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
	 * <p>
	 * 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, 0, inorder.length - 1, inorderMap);
	}

	private TreeNode buildTree(int[] preorder, int preStart, int preEnd, int inStart, int inEnd, Map<Integer, Integer> inorderMap) {
		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, inStart, inRoot - 1, inorderMap);
		root.right = buildTree(preorder, preStart + numsLeft + 1, preEnd, inRoot + 1, inEnd, inorderMap);
		return root;
	}

}

@@ -130,16 +130,86 @@
 ap;%0A%0A/**
+%0A * 105. Construct Binary Tree from Preorder and Inorder Traversal%0A * 
 Given pr
@@ -340,16 +340,18 @@
 he tree.
+%0A 
 */%0Apubli
@@ -544,16 +544,8 @@
 ime%0A
-%09 * %3Cp%3E%0A
 %09 * 
@@ -912,16 +912,28 @@
 gth - 1,
+ inorderMap,
  0, inor
@@ -942,36 +942,24 @@
 r.length - 1
-, inorderMap
 );%0A%09%7D%0A%0A%09priv
@@ -1026,32 +1026,8 @@
 End,
- int inStart, int inEnd,
  Map
@@ -1055,16 +1055,40 @@
 orderMap
+, int inStart, int inEnd
 ) %7B%0A%09%09if
@@ -1766,16 +1766,28 @@
 umsLeft,
+ inorderMap,
  inStart
@@ -1798,28 +1798,16 @@
 Root - 1
-, inorderMap
 );%0A%09%09roo
@@ -1868,16 +1868,28 @@
  preEnd,
+ inorderMap,
  inRoot 
@@ -1898,28 +1898,16 @@
 1, inEnd
-, inorderMap
 );%0A%09%09ret

refactor 105