[leetcode] Clone Graph | 克隆无向图
Posted October 8, 2013
on:倒是20分钟写出来了bugfree,比较喜欢这种利用data structure的题,感觉试一试总能想出来。
这个题就是基本BFS,要点是生成新节点的同时,怎么把新节点和其他新节点连起来呢?这就需要一个新旧节点对应map,每次生成新节点A’,要把dequeue的这个parent B对应的新节点B’和当前作为child的新节点A’连起来。注意单向连就行了(B’->A)’,因为下次把A当作root的时候,还会经历B作为child,这时再A’->B’。
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { if (node == null) return null; Queue<UndirectedGraphNode> q = new LinkedList<UndirectedGraphNode>(); Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>(); enqueueAndClone(q, node, map); while (!q.isEmpty()) { UndirectedGraphNode parent = q.poll(); for (UndirectedGraphNode child : parent.neighbors) { if (!map.containsKey(child)) enqueueAndClone(q, child, map); map.get(parent).neighbors.add(map.get(child));//不管是否visit过,都要单向连接 } } return map.get(node); } private void enqueueAndClone(Queue<UndirectedGraphNode> q, UndirectedGraphNode node, Map<UndirectedGraphNode, UndirectedGraphNode> map) { q.add(node); UndirectedGraphNode newNode = new UndirectedGraphNode(node.label); map.put(node, newNode); }
Leave a Reply