[Recursive][DFS] Construct Binary Tree from Inorder and Postorder Traversal

1. Example

Inorder sequence    :   4 2 5 (1) 6 7 3 8
Postorder sequence:   4 5 2 6 7 8 3 (1)
The constructed BT is

                       1
                   /        \
                  2         3
               /    \       /   \
             4      5    7    8
                          /
                         6

2. Implementation
Q1: Binary Tree?
A1: node have val, left node, right node.
Step1: a root
Step2: root.leftsubtree, root.rightsubtree, 3 nodes form a small tree
Step3:  left subtree, right subtree
Step4: find each subtree's root
Q1: inorder?
A1: root in the middle.
Q1: postorder?
A1: root in the end.

public TreeNode buildTree(int[] inorder, int[] postorder)
{




      // validate the input
      if (inorder == null || postorder == null || inorder.length ==0 || postorder.length == 0)
            return new TreeNode();






       HashMap map = new HashMap<>();
       for (int i = 0 ; i < inorder.length; i++)
       {
            map.put(inorder[i], i);
       }





      // Find the root
      //return helper(inorder, 0, inorder.length-1, postorder, 0, postorder.length -1);
      return helper(inorder, 0, inorder.length-1, postorder, 0, postorder.length -1, map);
}

private TreeNode helper(int[] inorder, int inL, int inR, int[] postorder, int postL, int postR, HashMap map)
{




      // Base case
      //if (  inL < 0 || inR < 0 ||  postL <0 data-blogger-escaped-if="" data-blogger-escaped-inl="" data-blogger-escaped-null="" data-blogger-escaped-postr="" data-blogger-escaped-return=""> inR || postL > postR)
         return null;





      TreeNode root = new TreeNode( postorder[postR] );
      int rootIndex = map.get(root.val);
      root.left = helper(inorder,inL ,rootIndex-1 , postorder ,postL ,postL+(rootIndex-inL)-1,map);
      root.right = helper(inorder , rootIndex +1, inR, postorder ,postR -(inR- rootIndex), postR -1,map);



      
      return root; 



}
//O(log(n)) improve to O(1) using hashmap
private int binarySearch (int[] arr,int start, int end, int target)
{
      // validate the input
      if ( arr == null || arr.length == 0)
          return -1;
      int l = start;
      int r = end;
      while (l <= r )
      {
          int m = (l+m)/2;
          if ( arr[m] == target )
             return m;
          else if ( arr[m] > target ) 
             r = m-1;
          else 
             l = m+1;
      }
}

3. Similar Ones
(M) Construct Binary Tree from Preorder and Inorder Traversal