BFS: 用一个HashMap存储已经生成过的点,避免重复生成相同的点。
public class Solution { public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { if (node == null) { return null; } HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>(); Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>(); queue.offer(node); map.put(node, new UndirectedGraphNode(node.label)); while (!queue.isEmpty()) { UndirectedGraphNode cur = queue.poll(); UndirectedGraphNode newcur = map.get(cur); for (UndirectedGraphNode neig : cur.neighbors) { //if contains, this node has already been searched if (!map.containsKey(neig)) { map.put(neig, new UndirectedGraphNode(neig.label)); queue.offer(neig); } newcur.neighbors.add(map.get(neig)); } } return map.get(node); } }
No comments:
Post a Comment