长大后想做什么？做回小孩！

0%

LeetCode——克隆图

发表于 更新于 分类于 Valine：
本文字数： 402

NO.133 克隆图 中等

JoafnH.png

JoahBd.png

JoaRje.png

Joa2cD.png

忍不住吐槽一下，题干好长！题目就是要求读者遍历图，遍历的时候顺便拷贝一下。既然是遍历图，那么大体上就是两种：深度优先遍历、广度优先遍历。

思路一：BFS 用一个map存储已经访问过的节点，key是访问过的节点、value是key节点的克隆。

  1. 从队列弹出一个节点。
  2. 遍历该节点的所有邻接点。
  3. 如果某个邻接点已被访问，则该邻接点一定在 map 中，那么从 map 获得该邻接点。否则，创建一个新的节点存储在 map 中。
  4. 将克隆的邻接点添加到克隆图对应节点的邻接表中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public Node cloneGraph(Node node) {
    if (node == null) return null;
    HashMap<Node, Node> map = new HashMap<>();
    Node clone = new Node(node.val, new ArrayList<>());
    map.put(node, clone);
    Deque<Node> queue = new LinkedList<>();
    queue.offer(node);
    //广搜
    while (!queue.isEmpty()) {
        Node poll = queue.poll();
        //遍历节点的邻接点
        for (Node n : poll.neighbors) {
            //如果邻接点没有被访问过(未克隆),则进行克隆并入队
            if (!map.containsKey(n)) {
                map.put(n, new Node(n.val, new ArrayList<>()));
                queue.offer(n);
            }
            //将克隆的邻接点,添加到对应的克隆节点的邻接表中
            map.get(poll).neighbors.add(map.get(n));
        }
    }
    return clone;
}

时间复杂度：O(n) 空间复杂度：O(n) 保存克隆图O(n)，队列O(w)，w是图的宽。

思路二：DFS 依然用一个map存储已经访问过的节点，key是访问过的节点、value是key节点的克隆。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
HashMap<Node, Node> map = new HashMap<>();

public Node cloneGraph(Node node) {
    if (node == null) return null;
    //如果node节点已经访问过(已克隆),则返回其克隆节点
    if (map.containsKey(node)) return map.get(node);
    //生成克隆节点
    Node clone = new Node(node.val, new ArrayList<>());
    //记录已访问的节点
    map.put(node, clone);
    //遍历源节点的邻接点
    for (Node n : node.neighbors) {
        //克隆每个邻接点,并添加到对应克隆节点的邻接表中
        clone.neighbors.add(cloneGraph(n));
    }
    return clone;
}

时间复杂度：O(n) 空间复杂度：O(n) 保存克隆图O(n)，递归栈O(h)，h是图的深度。

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github