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

## Problem

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


## Code

654

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

HashMap<Integer, Integer> map = new HashMap<>();

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

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

private TreeNode helper(int[] inorder,
int[] postorder,
int inStart,
int inEnd,
int postStart,
int postEnd,
HashMap<Integer, Integer> map){

if(inStart > inEnd || postStart < 0){
return null;
}

int rootIndex = map.get(postorder[postEnd]);
TreeNode root = new TreeNode(postorder[postEnd]);

root.left = helper(inorder, postorder,
inStart,
rootIndex - 1,
postStart,
postStart + rootIndex - inStart - 1,
map);

root.right = helper(inorder, postorder,
rootIndex + 1,
inEnd,
postStart + rootIndex - inStart,
postEnd - 1,
map);

return root;
}
}