題目描述（中等難度）

復(fù)制一個圖，圖的節(jié)點定義如下。

class Node {
    public int val;
    public List<Node> neighbors;

    public Node() {}

    public Node(int _val,List<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};

neighbors 是一個裝 Node 的 list ，因為對象的話，java 變量都存儲的是引用，所以復(fù)制的話要新 new 一個 Node 放到 neighbors。

思路分析

這個題其實就是對圖進(jìn)行一個遍歷，通過 BFS 或者 DFS。需要解決的問題就是怎么添加當(dāng)前節(jié)點的 neighbors，因為遍歷當(dāng)前節(jié)點的時候，它的鄰居節(jié)點可能還沒有生成。

解法一 BFS

先來一個簡單粗暴的想法。

首先對圖進(jìn)行一個 BFS，把所有節(jié)點 new 出來，不處理 neighbors ，并且把所有的節(jié)點存到 map 中。

然后再對圖做一個 BFS，因為此時所有的節(jié)點已經(jīng)創(chuàng)建了，只需要更新所有節(jié)點的 neighbors。

public Node cloneGraph(Node node) {
    if (node == null) {
        return node;
    }
    //第一次 BFS
    Queue<Node> queue = new LinkedList<>();
    Map<Integer, Node> map = new HashMap<>();
    Set<Integer> visited = new HashSet<>();
    queue.offer(node);
    visited.add(node.val);
    while (!queue.isEmpty()) {
        Node cur = queue.poll();
        //生成每一個節(jié)點
        Node n = new Node();
        n.val = cur.val;
        n.neighbors = new ArrayList<Node>();
        map.put(n.val, n);
        for (Node temp : cur.neighbors) {
            if (visited.contains(temp.val)) {
                continue;
            }
            queue.offer(temp);
            visited.add(temp.val);
        }
    }

    //第二次 BFS 更新所有節(jié)點的 neightbors
    queue = new LinkedList<>();
    queue.offer(node);
    visited = new HashSet<>();
    visited.add(node.val);
    while (!queue.isEmpty()) {
        Node cur = queue.poll();
        for (Node temp : cur.neighbors) {
            map.get(cur.val).neighbors.add(map.get(temp.val));
        }
        for (Node temp : cur.neighbors) {
            if (visited.contains(temp.val)) {
                continue;
            }
            queue.offer(temp);
            visited.add(temp.val);
        }
    }
    return map.get(node.val);
}

當(dāng)然再仔細(xì)思考一下，其實我們不需要兩次 BFS。

我們要解決的問題是遍歷當(dāng)前節(jié)點的時候，鄰居節(jié)點沒有生成，那么我們可以一邊遍歷一邊生成鄰居節(jié)點，就可以同時更新 neighbors了。

同樣需要一個 map 記錄已經(jīng)生成的節(jié)點。

public Node cloneGraph(Node node) {
    if (node == null) {
        return node;
    }
    Queue<Node> queue = new LinkedList<>();
    Map<Integer, Node> map = new HashMap<>();
    queue.offer(node);
    //先生成第一個節(jié)點
    Node n = new Node();
    n.val = node.val;
    n.neighbors = new ArrayList<Node>();
    map.put(n.val, n);
    while (!queue.isEmpty()) {
        Node cur = queue.poll();
        for (Node temp : cur.neighbors) {
            //沒有生成的節(jié)點就生成
            if (!map.containsKey(temp.val)) {
                n = new Node();
                n.val = temp.val;
                n.neighbors = new ArrayList<Node>();
                map.put(n.val, n);
                queue.offer(temp);
            }
            map.get(cur.val).neighbors.add(map.get(temp.val));
        }
    }

    return map.get(node.val);
}

解法二 DFS

DFS 的話用遞歸即可，也用一個 map 記錄已經(jīng)生成的節(jié)點。

public Node cloneGraph(Node node) {
    if (node == null) {
        return node;
    }
    Map<Integer, Node> map = new HashMap<>();
    return cloneGrapthHelper(node, map);
}

private Node cloneGrapthHelper(Node node, Map<Integer, Node> map) {
    if (map.containsKey(node.val)) {
        return map.get(node.val);
    }
    //生成當(dāng)前節(jié)點
    Node n = new Node();
    n.val = node.val;
    n.neighbors = new ArrayList<Node>();
    map.put(node.val, n);
    //添加它的所有鄰居節(jié)點
    for (Node temp : node.neighbors) {
        n.neighbors.add(cloneGrapthHelper(temp, map));
    }
    return n;
}

總

這道題本質(zhì)上就是對圖的遍歷，只要想到用 map 去存儲已經(jīng)生成的節(jié)點，題目基本上就解決了。

更多詳細(xì)通俗題解詳見 leetcode.wang 。