-
-
Notifications
You must be signed in to change notification settings - Fork 8.9k
/
Copy pathSolution.java
30 lines (28 loc) · 996 Bytes
/
Solution.java
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
29
30
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private Map<Integer, Integer> indexes = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
int n = inorder.length;
for (int i = 0; i < n; ++i) {
indexes.put(inorder[i], i);
}
return build(preorder, inorder, 0, n - 1, 0, n - 1);
}
private TreeNode build(int[] preorder, int[] inorder, int p1, int p2, int i1, int i2) {
if (p1 > p2 || i1 > i2) return null;
int rootVal = preorder[p1];
int pos = indexes.get(rootVal);
TreeNode node = new TreeNode(rootVal);
node.left = pos == i1 ? null : build(preorder, inorder, p1 + 1, pos - i1 + p1, i1, pos - 1);
node.right = pos == i2 ? null : build(preorder, inorder, pos - i1 + p1 + 1, p2, pos + 1, i2);
return node;
}
}