By

Contents
  1. 1. 题目
  2. 2. 解法

题目

给定无向连通图中一个节点的引用，返回该图的深拷贝（克隆）。图中的每个节点都包含它的值 val（Int） 和其邻居的列表（list[Node]）。
示例：7b2bfd1590ab9401ab6d2eb6d985b68a.png
输入：{“$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 。提示：节点数介于 1 到 100 之间。无向图是一个简单图，这意味着图中没有重复的边，也没有自环。由于图是无向的，如果节点 p 是节点 q 的邻居，那么节点 q 也必须是节点 p 的邻居。必须将给定节点的拷贝作为对克隆图的引用返回。

解法

深度遍历+深浅克隆
Map用于存放访问过的点，如果访问过直接返回
递归遍历neighbors
结束条件是，所有节点都访问过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/*
// 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) {
        Map<Integer,Node> map = new HashMap<Integer,Node>();
        return deepClone(node,map);
    }
    
    public Node deepClone(Node node,Map<Integer,Node> map){
        Node newNode;
        if(map.containsKey(node.val)){
            newNode = map.get(node.val);
            return newNode;
        }else{
            newNode = new Node(node.val,null);
            map.put(node.val,newNode);
        }
        List<Node> nei = new ArrayList<Node>();
        if(node.neighbors != null){
            for(Node n : node.neighbors){
                nei.add(deepClone(n,map));
            }
        }
        newNode.neighbors = nei;
        return newNode;
        
    }
}
Contents
  1. 1. 题目
  2. 2. 解法