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 PostOrder {
        int idx;

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

    private enum Direction {
        LEFT, RIGHT, CENTER
    }

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder.length == 0) {
            return null;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        TreeNode node = new TreeNode(postorder[postorder.length - 1]);
        PostOrder po = new PostOrder(postorder.length - 1);
        buildTree(node, postorder, po, 0, inorder.length, map, Direction.CENTER);
        return node;
    }

    private void buildTree(TreeNode node,
                           int[] postorder,
                           PostOrder po,
                           int fromInOrderIdx,
                           int toInOrderIdx,
                           Map<Integer, Integer> map,
                           Direction direction) {
        if (po.idx < 0) {
            return;
        }
        int inOrderIdx = map.get(postorder[po.idx]);
        TreeNode newNode = null;
        if (direction == Direction.LEFT) {
            node.left = new TreeNode(postorder[po.idx]);
            newNode = node.left;
        } else if (direction == Direction.RIGHT) {
            node.right = new TreeNode(postorder[po.idx]);
            newNode = node.right;
        } else {
            newNode = node;
        }
        if (inOrderIdx + 1 < toInOrderIdx) {
            po.idx--;
            buildTree(newNode, postorder, po, inOrderIdx + 1, toInOrderIdx,
                map, Direction.RIGHT);
        }
        if (fromInOrderIdx < inOrderIdx) {
            po.idx--;
            buildTree(newNode, postorder, po, fromInOrderIdx,
                inOrderIdx, map, Direction.LEFT);
        }
    }
}

@@ -370,25 +370,22 @@
 e class 
-PostOrder
+IntRef
  %7B%0A     
@@ -383,24 +383,32 @@
 f %7B%0A        
+private 
 int idx;%0A%0A  
@@ -420,25 +420,22 @@
  public 
-PostOrder
+IntRef
 (int idx
@@ -487,72 +487,8 @@
  %7D%0A%0A
-    private enum Direction %7B%0A        LEFT, RIGHT, CENTER%0A    %7D%0A%0A
     
@@ -647,17 +647,24 @@
 nteger%3E 
-m
+inOrderM
 ap = new
@@ -740,17 +740,24 @@
         
-m
+inOrderM
 ap.put(i
@@ -864,36 +864,45 @@
     
-PostO
+buildTree(node, posto
 rder
- po = new PostOrder
+, new IntRef
 (pos
@@ -923,89 +923,39 @@
 - 1)
-;%0A        buildTree(node, postorder, po, 0, inorder.length, map, Direction.CENTER
+, 0, inorder.length, inOrderMap
 );%0A 
@@ -1098,20 +1098,32 @@
     
-PostOrder po
+IntRef postOrderIndexRef
 ,%0A  
@@ -1265,118 +1265,21 @@
 er%3E 
-map,%0A                           Direction direction) %7B%0A        if (po.idx %3C 0) %7B%0A            return;%0A        %7D
+inOrderMap) %7B
 %0A   
@@ -1300,17 +1300,24 @@
 erIdx = 
-m
+inOrderM
 ap.get(p
@@ -1319,32 +1319,47 @@
 get(postorder%5Bpo
+stOrderIndexRef
 .idx%5D);%0A        
@@ -1362,131 +1362,80 @@
     
-TreeNode newNode = null;%0A        if (direction == Direction.LEFT) %7B%0A            node.left = new TreeNode(postorder%5Bpo
+if (inOrderIdx + 1 %3C toInOrderIdx) %7B%0A            postOrderIndexRef
 .idx
-%5D)
+--
 ;%0A  
@@ -1448,215 +1448,201 @@
     
-newNode = node.left;%0A        %7D else if (direction == Direction.RIGHT) %7B%0A            node.right = new TreeNode(postorder%5Bpo.idx%5D);%0A            newNode = node.right;%0A        %7D else %7B%0A            newNode = node
+int val = postorder%5BpostOrderIndexRef.idx%5D;%0A            node.right = new TreeNode(val);%0A            buildTree(node.right, postorder, postOrderIndexRef, inOrderIdx + 1, toInOrderIdx, inOrderMap)
 ;%0A  
@@ -1653,33 +1653,37 @@
   %7D%0A        if (
-i
+fromI
 nOrderIdx + 1 %3C 
@@ -1672,33 +1672,27 @@
 mInOrderIdx 
-+ 1 %3C toI
+%3C i
 nOrderIdx) %7B
@@ -1698,32 +1698,47 @@
 %7B%0A            po
+stOrderIndexRef
 .idx--;%0A        
@@ -1745,109 +1745,50 @@
     
-buildTree(newNode, postorder, po, inOrderIdx + 1, toInOrderIdx,%0A                map, Direction.RIGHT)
+int val = postorder%5BpostOrderIndexRef.idx%5D
 ;%0A  
@@ -1797,73 +1797,41 @@
     
-%7D%0A
     
-    if (fromInOrderIdx %3C inOrderIdx) %7B%0A            po.idx--
+node.left = new TreeNode(val)
 ;%0A  
@@ -1855,14 +1855,16 @@
 ee(n
-ewN
 ode
+.left
 , po
@@ -1874,16 +1874,31 @@
 rder, po
+stOrderIndexRef
 , fromIn
@@ -1910,56 +1910,31 @@
 Idx,
-%0A                inOrderIdx, map, Direction.LEFT
+ inOrderIdx, inOrderMap
 );%0A 

Update problem 106