package leetcode;

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

/**
 * https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
 */
public class Problem105 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0) {
            return null;
        }
        Map<Integer, Integer> inOrderMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inOrderMap.put(inorder[i], i);
        }
        TreeNode node = new TreeNode(preorder[0]);
        buildTree(node, preorder, new IntRef(0), 0, inorder.length, inOrderMap);
        return node;
    }

    private class IntRef {
        private int idx;

        public IntRef(int idx) {
            this.idx = idx;
        }
    }

    private void buildTree(TreeNode node,
                           int[] preorder,
                           IntRef preOrderIndexRef,
                           int fromInOrderIdx,
                           int toInOrderIdx,
                           Map<Integer, Integer> inOrderMap) {
        if (preOrderIndexRef.idx >= preorder.length) {
            return;
        }
        int inOrderIdx = inOrderMap.get(preorder[preOrderIndexRef.idx]);
        if (fromInOrderIdx < inOrderIdx) {
            preOrderIndexRef.idx++;
            int val = preorder[preOrderIndexRef.idx];
            node.left = new TreeNode(val);
            buildTree(node.left, preorder, preOrderIndexRef, fromInOrderIdx, inOrderIdx, inOrderMap);
        }
        if (inOrderIdx + 1 < toInOrderIdx) {
            preOrderIndexRef.idx++;
            int val = preorder[preOrderIndexRef.idx];
            node.right = new TreeNode(val);
            buildTree(node.right, preorder, preOrderIndexRef, inOrderIdx + 1, toInOrderIdx, inOrderMap);
        }
    }
}

@@ -426,70 +426,27 @@
     
-if (preorder.length == 0) %7B%0A            return null;%0A        %7D
+// For fast lookup.
 %0A   
@@ -618,83 +618,45 @@
     
-T
 re
-eNode node = new TreeNode(preorder%5B0%5D);%0A        buildTree(node, preo
+turn buildTree(preorder, inO
 rder
+Map
 , ne
@@ -668,17 +668,17 @@
 Ref(
-0
 ), 0, 
-in
+pre
 orde
@@ -689,354 +689,178 @@
 ngth
-, inOrderMap);%0A        return node;%0A    %7D%0A%0A    private class IntRef %7B%0A        private int idx;%0A%0A        public IntRef(int idx) %7B%0A            this.idx = idx;%0A        %7D%0A    %7D%0A%0A    private void buildTree(TreeNode node,%0A                           int%5B%5D preorder,%0A                           IntRef preOrderIndexRef,%0A                           int from
+ - 1);%0A    %7D%0A%0A    private static TreeNode buildTree(int%5B%5D preOrder,  Map%3CInteger, Integer%3E inOrderMap,%0A                                      IntRef preOrderIdx, int start
 InOr
@@ -898,14 +898,26 @@
     
+           
 int 
-to
+end
 InOr
@@ -914,33 +914,35 @@
 nt endInOrderIdx
-,
+) %7B
 %0A               
@@ -938,59 +938,81 @@
     
-                   Map%3CInteger, Integer%3E i
+if (preOrder.length %3C= preOrderIdx.val %7C%7C startInOrderIdx %3E endI
 nOrder
-Map
+Idx
 ) %7B%0A
@@ -1011,36 +1011,36 @@
 rIdx) %7B%0A        
-if (
+    
 preOrderIndexRef
@@ -1036,41 +1036,17 @@
 derI
-ndexRef.idx %3E= preorder.length) %7B
+dx.val--;
 %0A   
@@ -1060,16 +1060,21 @@
   return
+ null
 ;%0A      
@@ -1093,40 +1093,18 @@
 int 
-inOrderIdx = inOrderMap.get(preo
+val = preO
 rder
@@ -1117,21 +1117,15 @@
 derI
-ndexRef.idx%5D)
+dx.val%5D
 ;%0A  
@@ -1135,16 +1135,12 @@
    i
-f (fromI
+nt i
 nOrd
@@ -1149,17 +1149,17 @@
 Idx 
-%3C
+=
  inOrder
 Idx)
@@ -1158,215 +1158,147 @@
 rder
-Idx) %7B%0A            preOrderIndexRef.idx++;%0A            int val = preorder%5BpreOrderIndexRef.idx%5D;%0A            node.left = new TreeNode(val);%0A            buildTree(node.left, preo
+Map.get(val);%0A        TreeNode node = new TreeNode(val);%0A        preOrderIdx.val++;%0A        node.left = buildTree(preO
 rder, 
-pre
+in
 Order
-IndexRef, fromIn
+Map, pre
 Orde
@@ -1299,25 +1299,30 @@
 reOrderIdx, 
-i
+startI
 nOrderIdx, i
@@ -1324,43 +1324,8 @@
 dx, 
-inOrderMap);%0A        %7D%0A        if (
 inOr
@@ -1335,29 +1335,13 @@
 Idx 
-+ 1 %3C toInOrderIdx) %7B
+- 1);
 %0A   
@@ -1337,36 +1337,32 @@
 x - 1);%0A        
-    
 preOrderIndexRef
@@ -1358,163 +1358,69 @@
 derI
-ndexRef.idx++;%0A            int val = preorder%5BpreOrderIndexRef.idx%5D;%0A            node.right = new TreeNode(val);%0A            buildTree(node.right, preo
+dx.val++;%0A        node.right = buildTree(preOrder, inO
 rder
+Map
 , pr
@@ -1430,15 +1430,10 @@
 derI
-ndexRef
+dx
 , in
@@ -1450,10 +1450,11 @@
  1, 
-to
+end
 InOr
@@ -1463,32 +1463,97 @@
 rIdx
-, inOrderMap);%0A        %7D
+);%0A        return node;%0A    %7D%0A%0A    private static class IntRef %7B%0A        private int val;
 %0A   

Update problem 105