1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| /**
* use inorder to determine the current node belongs to left or right.
* use class variable to memorize the current position in preorder.
*/
class Solution {
Map<Integer, Integer> loc;
int p;
public TreeNode buildTree(int[] preorder, int[] inorder) {
loc = new HashMap<>(preorder.length);
List<Integer> preorderList = new ArrayList<>(preorder.length);
for (int i = 0; i < inorder.length; i++) {
loc.put(inorder[i], i);
}
p = 0;
return build(preorder, 0, preorder.length);
}
private TreeNode build(int[] pre, int l, int r) {
if (r <= l) {
return null;
}
TreeNode root = new TreeNode(pre[p++]);
int idx = loc.get(root.val);
root.left = build(pre, l, idx);
root.right = build(pre, idx+1, r);
return root;
}
}
|