# 106. Construct Binary Tree from Inorder and Postorder Traversal (Medium)

https://leetcode.com/problems/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
```

## Solutions

``````class Solution {

// Keep the index for specific node in inorder sequence which boosts up the efficiency
// of searching for split point.
Map<Integer, Integer> inorderMap = new HashMap<>();

public TreeNode buildTree(int[] inorder, int[] postorder) {
if (inorder == null || postorder == null || inorder.length != postorder.length) {
return null;
}

for (int i = 0; i < inorder.length; i++) {
inorderMap.put(inorder[i], i);
}

return recurse(inorder, 0, inorder.length - 1, postorder, 0, inorder.length - 1);
}

private TreeNode recurse(int[] inorder, int startIn, int endIn, int[] postorder, int startPost, int endPost) {
if (startIn > endIn || startPost > endPost) {
return null;
}

// Take in following example when working on boundary problems.

// in order [9, x, 15, 20, 7]
// post order [9, 15, 7, 20, x]

// the last output node in post-order sequence is the root
int val = postorder[endPost];

TreeNode root = new TreeNode(val);

// midIn = 1
int midIn = inorderMap.get(val);

// midIn - startIn represents the length of left tree
// midPost = 0+1-0=1
int midPost = startPost + midIn - startIn;

// 1. For in-order output, [startIn:midIn-1] are left nodes, [midIn+1:endIn] are right nodes.
// 2. For post-order output, [startPost:midPost] are left nodes, [midPost+1:endPost - 1] are the right nodes

// in order [0,0], post order [0,0]
root.left = recurse(inorder, startIn, midIn - 1, postorder, startPost, midPost - 1);

// in order [2,4], post order [1, 3]
root.right = recurse(inorder, midIn + 1, endIn, postorder, midPost, endPost - 1);

return root;
}
}
``````