# 105. Construct Binary Tree from Preorder and Inorder Traversal (Medium)

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

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

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

For example, given

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

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[] preorder, int[] inorder) {
if (preorder == null || inorder == null || preorder.length != inorder.length) {
return null;
}

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

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

private TreeNode recurse(int[] preorder, int startPre, int endPre, int[] inorder, int startIn, int endIn) {
if (startPre > endPre || startIn > endIn) {
return null;
}

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

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

// the first output node in post-order sequence is the root
int val = preorder[startPre];

TreeNode root = new TreeNode(val);

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

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

// 1. For pre-order output, [startPre+1:midPre] are left nodes, [midPre+1:endPre] are the right nodes
// 2. For in-order output, [startIn+0:midIn-1] are left nodes, [midIn+1:endIn] are right nodes.

// pre order [1,1], inorder [0,0]
root.left = recurse(preorder, startPre + 1, midPre, inorder, startIn, midIn - 1);

// pre order [2,4], in order [2,4]
root.right = recurse(preorder, midPre + 1, endPre, inorder, midIn + 1, endIn);

return root;
}
}
``````

## References

Copyright © iovi.com 2017 all right reserved，powered by GitbookLast Modification: 2019-12-03 11:01:18