Leetcode133克隆图

题目

给定无向连通图中一个节点的引用，返回该图的深拷贝（克隆）。图中的每个节点都包含它的值 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}

解释：

节点 1 的值是 1，它有两个邻居：节点 2 和 4 。
节点 2 的值是 2，它有两个邻居：节点 1 和 3 。
节点 3 的值是 3，它有两个邻居：节点 2 和 4 。
节点 4 的值是 4，它有两个邻居：节点 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;
        }
        //用来记录所有的节点情况
        Map<Integer,Node> map = new HashMap<>();
        //首先建立根节点
        int rootVal = node.val;
        Node root = new Node(rootVal,new ArrayList<Node>());
        map.put(rootVal,root);
        //在根节点利用深度优先算法去构建一棵树
        copyNeighbors(node,map);
        return root;
    }

    public void copyNeighbors(Node root,Map<Integer,Node> map){
        //获取复制后的当前节点
        Node r = map.get(root.val);
        //遍历他的邻居节点
        for(Node node:root.neighbors){
            //如果邻居节点已经被构建过，证明此节点之前已经被遍历和复制了，只需要放在其邻居的列表中即可
            //如果没有被构建则需要复制构建一次，加入索引的map中，并先对他进行邻居节点的复制
            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);
        }
    }
}