• ㊗️
• 大家
• offer
• 多多！

## Problem

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


## Code

654

class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
HashMap<Integer, Integer> map = new HashMap<>();

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

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

private TreeNode helper(int[] preorder,
int[] inorder,
int preStart,
int inStart,
int inEnd,
HashMap<Integer, Integer> map){

if(preStart >= preorder.length || inStart > inEnd) return null;

TreeNode root = new TreeNode(preorder[preStart]);

int rootIndex = map.get(preorder[preStart]);

root.left = helper(preorder, inorder, preStart + 1, inStart, rootIndex - 1, map);
root.right = helper(preorder, inorder, preStart + rootIndex - inStart + 1, rootIndex + 1, inEnd, map);

return root;
}
}