-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathP_105.java
More file actions
34 lines (28 loc) · 890 Bytes
/
Copy pathP_105.java
File metadata and controls
34 lines (28 loc) · 890 Bytes
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
31
32
33
34
package leetcode.medium;
import java.util.HashMap;
import java.util.Map;
import utils.DataStructures.TreeNode;
@SuppressWarnings({ "ConstantConditions", "ReturnOfNull" })
public class P_105 {
static Map<Integer, Integer> in;
static int idx;
public TreeNode buildTree(int[] preorder, int[] inorder) {
in = new HashMap<>();
idx = 0;
for (int i = 0; i < inorder.length; i++) {
in.put(inorder[i], i);
}
return dfs(preorder, 0, inorder.length - 1);
}
private static TreeNode dfs(int[] preorder, int l, int r) {
if (l > r) {
return null;
}
final int root = preorder[idx++];
final TreeNode res = new TreeNode(root);
final int idx = in.get(root);
res.left = dfs(preorder, l, idx - 1);
res.right = dfs(preorder, idx + 1, r);
return res;
}
}