典型DFS题目。。用一个HashMap把已经clone过的node记住... 要是遇到了 就不进行克隆过程 直接拿来用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | public class Solution {
HashMap<UndirectedGraphNode, UndirectedGraphNode> visited = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null){
return null;
}
UndirectedGraphNode root = dfsCopy(node);
return root;
}
private UndirectedGraphNode dfsCopy(UndirectedGraphNode node){
if (visited.containsKey(node)){
return visited.get(node);
}
UndirectedGraphNode root = new UndirectedGraphNode(node.label);
visited.put(node, root);
for (int i = 0; i < node.neighbors.size(); i++){
root.neighbors.add(dfsCopy(node.neighbors.get(i)));
}
return root;
}
}
|
No comments:
Post a Comment