題目

給定無向連通圖中一個節(jié)點的引用，返回該圖的深拷貝（克?。D中的每個節(jié)點都包含它的值 val（Int） 和其鄰居的列表（list[Node]）。
示例：

輸入：

{"$id":"1","neighbors":[{"$id":"2","neighbors":[{"$ref":"1"},{"$id":"3","neighbors":[{"$ref":"2"},{"$id":"4","neighbors":[{"$ref":"3"},{"$ref":"1"}],"val":4}],"val":3}],"val":2},{"$ref":"4"}],"val":1}

解釋：

節(jié)點 1 的值是 1，它有兩個鄰居：節(jié)點 2 和 4 。
節(jié)點 2 的值是 2，它有兩個鄰居：節(jié)點 1 和 3 。
節(jié)點 3 的值是 3，它有兩個鄰居：節(jié)點 2 和 4 。
節(jié)點 4 的值是 4，它有兩個鄰居：節(jié)點 1 和 3 。

思路及代碼

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;

    public Node() {}

    public Node(int _val,List<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/
class Solution {
    public Node cloneGraph(Node node) {
        if(node == null){
            return null;
        }
        //用來記錄所有的節(jié)點情況
        Map<Integer,Node> map = new HashMap<>();
        //首先建立根節(jié)點
        int rootVal = node.val;
        Node root = new Node(rootVal,new ArrayList<Node>());
        map.put(rootVal,root);
        //在根節(jié)點利用深度優(yōu)先算法去構(gòu)建一棵樹
        copyNeighbors(node,map);
        return root;
    }

    public void copyNeighbors(Node root,Map<Integer,Node> map){
        //獲取復(fù)制后的當(dāng)前節(jié)點
        Node r = map.get(root.val);
        //遍歷他的鄰居節(jié)點
        for(Node node:root.neighbors){
            //如果鄰居節(jié)點已經(jīng)被構(gòu)建過，證明此節(jié)點之前已經(jīng)被遍歷和復(fù)制了，只需要放在其鄰居的列表中即可
            //如果沒有被構(gòu)建則需要復(fù)制構(gòu)建一次，加入索引的map中，并先對他進(jìn)行鄰居節(jié)點的復(fù)制
            Node c = map.get(node.val);
            if(c==null){
                c = new Node(node.val,new ArrayList<Node>());
                map.put(node.val,c);
                copyNeighbors(node,map);
            }
            r.neighbors.add(c);
        }
    }
}