Given the levelorder 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
levelorder traversal = {5, 3, 8, 1, 4, 11}
inorder traversal = {1, 3, 4, 5, 8, 11}
the corresponding binary tree is
5
/ \
3 8
/ \
1 4 11
Solution: level[]第一个为root, 找到该数值在in[]的位置(利用hashmap),再把level[]剩下的拆分为左半部和右半部两个list(根据index大小)
public TreeNode reconstruct(int[] in, int[] level) {
if (in.length == 0) {
return null;
}
Map<Integer, Integer> hashmap = new HashMap<>();
List<Integer> levell = new ArrayList<>();
for (int i = 0; i < in.length; i++) {
hashmap.put(in[i], i);
levell.add(level[i]);
}
return build(in, 0, in.length - 1, levell, hashmap);
}
private TreeNode build(int[] in, int instart, int inend, List<Integer> level, Map<Integer, Integer> hashmap) {
if (instart > inend) {
return null;
}
TreeNode root = new TreeNode(level.get(0));
// int position = find(inorder, instart, inend, post[postend]);
List<Integer> left = new ArrayList<>();
List<Integer> right = new ArrayList<>();
int position = hashmap.get(level.get(0));
for (int i = 1; i < level.size(); i++) {
int num = level.get(i);
int pos = hashmap.get(num);
if (pos < position) {
left.add(num);
} else {
right.add(num);
}
}
root.left = build(in, instart, position - 1, left, hashmap);
root.right = build(in, position + 1, inend, right, hashmap);
return root;
}