package leetcode;

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

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

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

    private class IntRef {
        private int idx;

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

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder.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(postorder[postorder.length - 1]);
        buildTree(node, postorder, new IntRef(postorder.length - 1), 0, inorder.length, inOrderMap);
        return node;
    }

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

@@ -356,139 +356,8 @@
  %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
     
@@ -428,69 +428,27 @@
     
-if (inorder.length == 0) %7B%0A            return null;%0A        %7D
+// For fast lookup.
 %0A   
@@ -620,47 +620,41 @@
     
-TreeNode node = new TreeNode(postorder%5B
+IntRef postOrderIdx = new IntRef(
 post
@@ -669,17 +669,16 @@
 ngth - 1
-%5D
 );%0A     
@@ -672,32 +672,39 @@
 h - 1);%0A        
+return 
 buildTree(node, 
@@ -701,14 +701,8 @@
 ree(
-node, 
 post
@@ -712,47 +712,41 @@
 er, 
-new IntRef(
+inOrderMap, 
 post
-o
+O
 rder
-.length - 1)
+Idx
 , 0, 
-in
+post
 orde
@@ -757,91 +757,75 @@
 ngth
-, inOrderMap);%0A        return node;%0A    %7D%0A%0A    private void buildTree(TreeNode no
+ - 1);%0A    %7D%0A%0A    private static TreeNode buildTree(int%5B%5D postOr
 de
+r
 ,%0A  
@@ -853,25 +853,60 @@
     
-int%5B%5D postorder,%0A
+           Map%3CInteger, Integer%3E inOrderMap,%0A       
     
@@ -920,32 +920,36 @@
                 
+    
 IntRef postOrder
@@ -949,23 +949,18 @@
 stOrderI
-ndexRef
+dx
 ,%0A      
@@ -978,34 +978,8 @@
     
-      int fromInOrderIdx,%0A
     
@@ -995,24 +995,17 @@
     
-          int to
+int start
 InOr
@@ -1043,44 +1043,11 @@
     
-Map%3CInteger, Integer%3E inOrderMap) %7B%0A
+   
     
@@ -1054,17 +1054,20 @@
     int 
-i
+endI
 nOrderId
@@ -1071,74 +1071,54 @@
 rIdx
- = inOrderMap.get(postorder%5BpostOrderIndexRef.idx%5D);%0A        if (i
+) %7B%0A        if (postOrderIdx.val %3C 0 %7C%7C startI
 nOrd
@@ -1127,16 +1127,13 @@
 Idx 
-+ 1 %3C to
+%3E end
 InOr
@@ -1164,35 +1164,61 @@
 stOrderI
-ndexRef.idx--
+dx.val++
 ;%0A    
+        return null;%0A        %7D%0A
         
@@ -1223,33 +1223,33 @@
   int val = post
-o
+O
 rder%5BpostOrderIn
@@ -1251,109 +1251,186 @@
 derI
-ndexRef.idx%5D;%0A            node.right = new TreeNode(val);%0A            buildTree(node.right, posto
+dx.val%5D;%0A        int inOrderIdx = inOrderMap.get(val);%0A        TreeNode node = new TreeNode(val);%0A        postOrderIdx.val--;%0A        node.right = buildTree(postOrder, inO
 rder
+Map
 , po
@@ -1437,23 +1437,18 @@
 stOrderI
-ndexRef
+dx
 , inOrde
@@ -1457,18 +1457,19 @@
 dx + 1, 
-to
+end
 InOrderI
@@ -1474,49 +1474,111 @@
 rIdx
-, inOrderMap);%0A        %7D%0A        if (from
+);%0A        postOrderIdx.val--;%0A        node.left = buildTree(postOrder, inOrderMap, postOrderIdx, start
 InOr
@@ -1583,18 +1583,17 @@
 OrderIdx
- %3C
+,
  inOrder
@@ -1587,35 +1587,38 @@
 rIdx, inOrderIdx
-) %7B
+ - 1);
 %0A            pos
@@ -1614,135 +1614,120 @@
     
-    postOrderIndexRef.idx--
+return node
 ;%0A    
+%7D%0A%0A
     
-    int val = postorder%5BpostOrderIndexRef.idx%5D;%0A            node.left = new TreeNode(
+private static class IntRef %7B%0A        private int val;%0A%0A        public IntRef(int 
 val)
-;
+ %7B
 %0A   
@@ -1739,98 +1739,22 @@
     
-buildTree(node.left, postorder, postOrderIndexRef, fromInOrderIdx, inOrderIdx, inOrderMap)
+this.val = val
 ;%0A  

Update problem 106