-
Notifications
You must be signed in to change notification settings - Fork 0
/
Construct a Full Binary Tree.java
35 lines (35 loc) · 1.1 KB
/
Construct a Full Binary Tree.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
31
32
33
34
35
class Solution{
public Node constructBTree(int pre[], int preM[], int size){
if(size==0) return null;
HashMap<Integer,Integer> pmap = new HashMap<>();
HashMap<Integer,Integer> mmap = new HashMap<>();
for(int i=0;i<size;i++){
pmap.put(pre[i],i);
}
for(int i=0;i<size;i++){
mmap.put(preM[i],i);
}
Queue<Node> queue = new LinkedList<>();
Node root = new Node(pre[0]);
queue.add(root);
int count_no_nodes=1;
while(count_no_nodes<size){
int n=queue.size();
while(n>0 && count_no_nodes!=size){
Node curr= queue.poll();
int data = curr.data;
int pre_ind=pmap.get(data);
int mir_ind=mmap.get(data);
Node left = new Node(pre[++pre_ind]);
Node right = new Node(preM[++mir_ind]);
curr.left=left;
curr.right=right;
queue.add(left);
queue.add(right);
n--;
count_no_nodes+=2;
}
}
return root;
}
}