Given inorder and postorder traversal of a tree, construct the binary tree.
Note:You may assume that duplicates do not exist in the tree.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public TreeNode buildTree(int[] inorder, int[] postorder) {
if (inorder==null||postorder==null||inorder.length==0||postorder.length==0||inorder.length!=postorder.length) {
return null;
}
HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
for (int i = 0; i < inorder.length; i++) {
hashMap.put(inorder[i], i);
}
return inPos(inorder, 0, inorder.length-1, postorder, 0, postorder.length-1, hashMap);
}
private TreeNode inPos(int[] in,int ni,int nj,int[] pos,int si,int sj,HashMap<Integer, Integer> hashMap) {
if (si>sj) {
return null;
}
int index = hashMap.get(pos[sj]);
TreeNode node = new TreeNode(pos[sj]);
node.left = inPos(in, ni, index-1, pos, si, si+index-ni-1, hashMap);
node.right = inPos(in, index+1, nj, pos, si+index-ni, sj-1, hashMap);
return node;
}
