Clone Graph
Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
Analysis
- 用一个hashmap用来记录visited过的node,node的label作为key(题目中已说明lable unique),复制的node作为value
- 从原graph的一个node开始,首先复制一个和原node值一样的node
- 把这个复制的node和它的值放到map里去
- 然后遍历原node所有的neighbor,把每一个neibor都clone一遍,clone后返回的node作为新的neigbor
- base情况1:如果node为null,clone直接返回null
- base情况2:如果找到的node已经visited过了,那么直接找到对应的clone的node返回
Code
public class Solution {
private HashMap<Integer, UndirectedGraphNode> map = new HashMap<>();
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
return clone(node);
}
private UndirectedGraphNode clone(UndirectedGraphNode node) {
if (node == null) return null;
if (map.containsKey(node.label)) {
return map.get(node.label);
}
UndirectedGraphNode clone = new UndirectedGraphNode(node.label);
map.put(clone.label, clone);
for (UndirectedGraphNode neighbor : node.neighbors) {
clone.neighbors.add(clone(neighbor));
}
return clone;
}
}
Reference
Leetcode