Leetcode 133. Clone Graph

屏幕快照 2017-10-21 下午1.59.01.png

题意：克隆一个无向图。

思路：
因为是克隆所以需要一个map来存储克隆的映射关系，我们可以从给定的第一个节点向它的neighbor一直搜索下去。
如果map的key中有节点，那么搜索直接返回map的value；
如果key中还没有这个节点，那么新建一个节点，并把这对映射关系存入map，然后继续向neighbor搜索下去。

public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
    if (node == null) {
        return node;
    }

    HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();

    return cloneHelper(node, map);
}

private UndirectedGraphNode cloneHelper(UndirectedGraphNode node, HashMap<UndirectedGraphNode, UndirectedGraphNode> map) {
    if (map.containsKey(node)) {
        return map.get(node);
    }

    UndirectedGraphNode cloneNode = new UndirectedGraphNode(node.label);
    map.put(node, cloneNode);
    for (UndirectedGraphNode neighbor : node.neighbors) {
        cloneNode.neighbors.add(cloneHelper(neighbor, map));
    }

    return cloneNode;
}