Clone Graph

这题第一眼看到想到的是BFS。接着想到我需要一个queue来做BFS。之后，为了能一一对应的复制，还用到一个Map。对应新旧node。

BUG：就是我在复制新child node之前，就把旧child node添加到新的node的neighbors中了。

 1     public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
 2         if (node == null) {
 3             return null;
 4         }
 5         Queue<UndirectedGraphNode> q = new LinkedList<UndirectedGraphNode>();
 6         Map<UndirectedGraphNode,UndirectedGraphNode> map = new HashMap<UndirectedGraphNode,UndirectedGraphNode>();
 7         UndirectedGraphNode nodeCopy = new UndirectedGraphNode(node.label);
 8         q.add(node);
 9         map.put(node, nodeCopy);
10         while (!q.isEmpty()) {
11             UndirectedGraphNode cur = q.poll();
12             UndirectedGraphNode curCopy = map.get(cur);
13             for (UndirectedGraphNode child : cur.neighbors) {
14                 if (!map.containsKey(child)) {
15                     UndirectedGraphNode childCopy = new UndirectedGraphNode(child.label);
16                     map.put(child, childCopy);
17                     q.offer(child);
18                 }
19                 //BUG：先复制child node
20                 curCopy.neighbors.add(map.get(child));
21             }
22         }
23         return map.get(node);
24     }