-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathsolution7.java
More file actions
28 lines (25 loc) · 892 Bytes
/
Copy pathsolution7.java
File metadata and controls
28 lines (25 loc) · 892 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
package nowcoder;
import java.util.HashMap;
import java.util.Map;
public class solution7 {
private Map<Integer,Integer> indexForInOrders = new HashMap<>();
public TreeNode reConstructBinaryTree(int [] pre, int [] in) {
for(int i = 0;i<in.length;i++)
{
indexForInOrders.put(in[i],i);
}
return reConstructBinaryTree(pre,0,pre.length,0);
}
private TreeNode reConstructBinaryTree(int[] pre, int prel, int prer, int inl) {
if(prel>prer)
{
return null;
}
TreeNode root = new TreeNode(pre[prel]);
int inindex = indexForInOrders.get(root.val);
int leftTreeSize = inindex - inl;
root.left = reConstructBinaryTree(pre,prel+1,prel+leftTreeSize,inl);
root.right = reConstructBinaryTree(pre,prel+leftTreeSize+1,prer,inl+leftTreeSize+1);
return root;
}
}