Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors.
文章图片
给出一个无向图，让做一个deep copy
deep copy就是不是仅仅copy reference，而是重新建立一个无向图
思路：
DFS遍历节点，其中为了防止重复遍历，把遍历过节点保存在HashMap, 当节点已经存在在HashMap中就说明已经访问过了，不需要再遍历。
而且在map中用旧的节点指向copy出的新的节点，一一对应关系
【leetcode 133. Clone Graph（图的深复制）】遍历完之后，再建立neighbors的关系
因为所有的旧节点和新节点已经有了一一对应的关系，把HashMap中的Key，也就是旧节点遍历一遍，取每个节点的neighbors，找到neighbors中每个Node对应的新节点，添加到新的neighbors
/*
class Node {
public int val;
public List neighbors;
public Node() {}public Node(int _val,List _neighbors) {
val = _val;
neighbors = _neighbors;
}
};
*/
class Solution {
public Node cloneGraph(Node node) {
Queue queue = new LinkedList<>();
HashMap map = new HashMap();
queue.offer(node);
while (!queue.isEmpty()) {
Node tmp = queue.poll();
Node newNode = new Node(tmp.val, null);
map.put(tmp, newNode);
for (int i = 0;
i < tmp.neighbors.size();
i++) {
if (!map.containsKey(tmp.neighbors.get(i))) {
queue.offer(tmp.neighbors.get(i));
map.put(tmp.neighbors.get(i), null);
}
}
}for(Map.Entry entry : map.entrySet()){
Node current = entry.getKey();
List neighbors = new ArrayList();
for(Node tmpNode : current.neighbors) {
neighbors.add(map.get(tmpNode));
}
map.get(current).neighbors = neighbors;
}return map.get(node);
}
}
推荐阅读
- 数据结构与算法|【算法】力扣第 266场周赛
- leetcode|今天开始记录自己的力扣之路
- Python|Python 每日一练 二分查找 搜索旋转排序数组 详解
- 【LeetCode】28.实现strstr（） （KMP超详细讲解，sunday解法等五种方法，java实现）
- LeetCode-35-搜索插入位置-C语言
- leetcode python28.实现strStr()35. 搜索插入位置
- Leetcode Permutation I & II
- python|leetcode Longest Substring with At Most Two Distinct Characters 滑动窗口法
- LeetCode 28 Implement strStr() (C,C++,Java,Python)
- Python|Python Leetcode(665.非递减数列)