133.克隆图
大约 1 分钟
133.克隆图
题目描述
给你无向 连通 图中一个节点的引用,请你返回该图的 深拷贝(克隆)。
图中的每个节点都包含它的值 val(int) 和其邻居的列表(list[Node])。
class Node {
public int val;
public List<Node> neighbors;
}
示例:
输入:adjList = [[2,4],[1,3],[2,4],[1,3]]
输出:[[2,4],[1,3],[2,4],[1,3]]
解释:
图中有 4 个节点。
节点 1 的值是 1,它有两个邻居:节点 2 和 4 。
节点 2 的值是 2,它有两个邻居:节点 1 和 3 。
节点 3 的值是 3,它有两个邻居:节点 2 和 4 。
节点 4 的值是 4,它有两个邻居:节点 1 和 3 。
解题思路
深度优先搜索。
class Solution {
public Node cloneGraph(Node node) {
Map<Node, Node> lookup = new HashMap<>();
return dfs(node, lookup);
}
private Node dfs(Node node, Map<Node,Node> lookup) {
if (node == null) return null;
if (lookup.containsKey(node)) return lookup.get(node);
Node clone = new Node(node.val, new ArrayList<>());
lookup.put(node, clone);
for (Node n : node.neighbors)clone.neighbors.add(dfs(n,lookup));
return clone;
}
}
广度优先搜索。遍历图的过程,未访问过的节点放入队列。
class Solution {
public Node cloneGraph(Node node) {
return bfs(node, new HashMap<Node, Node>());
}
private Node bfs(Node root, HashMap<Node, Node> visitedMap) {
if (root == null) {
return root;
}
Queue<Node> queue = new ArrayDeque<>();
queue.offer(root);
Node cloneNode = new Node(root.val, new ArrayList<>());
visitedMap.put(root, cloneNode);
while (queue.size() != 0) {
Node node = queue.poll();
for (Node n : node.neighbors) {
Node tmp = visitedMap.get(n);
if (tmp == null) {
queue.offer(n); //未访问过的放入队列
tmp = new Node(n.val, new ArrayList<>());
visitedMap.put(n, tmp); //标记访问过
}
visitedMap.get(node).neighbors.add(tmp);
}
}
return visitedMap.get(root);
}
}
Loading...