-
Notifications
You must be signed in to change notification settings - Fork 0
/
CloneGraph.java
49 lines (40 loc) · 1.21 KB
/
CloneGraph.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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
package graph;
import java.util.*;
//Clone Grap https://leetcode.com/problems/clone-graph/
public class CloneGraph {
public Node cloneGraph(Node node) {
if(node == null ) return null;
Node clone = clone(node);
return clone;
}
public Node clone (Node node){
Queue <Node> q= new LinkedList<>();
Set<Integer> vals= new HashSet<>();
HashMap<Integer , Node> map= new HashMap<>();
q.offer(node);
while(!q.isEmpty()){
Node temp= q.poll() ;
if(!vals.contains(temp.val)){
map.put(temp.val, new Node(temp.val));
vals.add(temp.val);
for(Node n: temp.neighbors){
q.offer(n);
}
}
}
q.offer(node);
vals.clear() ;
while(!q.isEmpty()){
Node temp= q.poll();
if(!vals.contains(temp.val) ){
vals.add(temp.val);
Node cloned= map.get(temp.val );
for(Node n: temp.neighbors){
cloned.neighbors.add(map.get(n.val) );
q.offer(n);
}
}
}
return map.get(node.val);
}
}