-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathcloneGraph.java
More file actions
30 lines (28 loc) · 1.03 KB
/
cloneGraph.java
File metadata and controls
30 lines (28 loc) · 1.03 KB
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 undirected graph.
* class UndirectedGraphNode {
* int label;
* ArrayList<UndirectedGraphNode> neighbors;
* UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
* };
*/
public class Solution {
private HashMap<Integer, UndirectedGraphNode> map;
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
// Note: The Solution object is instantiated only once and is reused by each test case.
map = new HashMap<Integer, UndirectedGraphNode>();
return doClone(node);
}
private UndirectedGraphNode doClone(UndirectedGraphNode node) {
if(node == null) return null;
if(map.containsKey(node.label)) {
return map.get(node.label);
}
UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);
map.put(node.label, newNode);
for(UndirectedGraphNode n: node.neighbors) {
newNode.neighbors.add(doClone(n));
}
return newNode;
}
}