Given the postorder and inorder traversal sequence of a binary tree, reconstruct the original tree.
Assumptions
- The given sequences are not null and they have the same length
- There are no duplicate keys in the binary tree
Examples
postorder traversal = {1, 4, 3, 11, 8, 5}
inorder traversal = {1, 3, 4, 5, 8, 11}
the corresponding binary tree is
5
/ \
3 8
/ \
1 4 11
Solution: post[]最后一个为root,找到该数值在in[]的位置(利用hashmap),划分为左半部和右半部
public TreeNode reconstruct(int[] in, int[] post) {
if (in.length == 0) {
return null;
}
Map<Integer, Integer> hashmap = new HashMap<>();
for (int i = 0; i < in.length; i++) {
hashmap.put(in[i], i);
}
return build(in, 0, in.length - 1, post, 0, post.length - 1, hashmap);
}
private TreeNode build(int[] in, int instart, int inend, int[] post, int poststart, int postend, Map<Integer, Integer> hashmap) {
if (instart > inend) {
return null;
}
TreeNode root = new TreeNode(post[postend]);
// int position = find(inorder, instart, inend, post[postend]);
int position = hashmap.get(post[postend]);
root.left = build(in, instart, position - 1, post, poststart, poststart + position - instart - 1, hashmap);
root.right = build(in, position + 1, inend, post, poststart + position - instart, postend - 1, hashmap);
return root;
}