# Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

**Note:**\
You may assume that duplicates do not exist in the tree.

For example, given

```
inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]
```

Return the following binary tree:

```
    3
   / \
  9  20
    /  \
   15   7
```

```java
class Solution {
    // Map of element in In-Order -> Index
    Map<Integer, Integer> map;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int n = inorder.length;
        map = new HashMap<>();
        for (int i = 0; i < n; i++)
            map.put(inorder[i], i);
        return helper(inorder, postorder, 0, n - 1, 0, n - 1);
    }
    // is -> Inorder start, ie -> Inorder End
    // ps -> PostOrder start, pe -> PostOrder End
    public TreeNode helper(int[] in, int[] post, int is, int ie, int ps, int pe) {
        if (is > ie)
            return null;
        TreeNode root = new TreeNode(post[pe]);
        int rootIndex = map.get(post[pe]);
        root.left = helper(in, post, is, rootIndex - 1, ps, ps + rootIndex - is - 1);
        root.right = helper(in, post, rootIndex + 1, ie, pe - (ie - rootIndex), pe - 1);
        return root;
    }
}
```
