给你无向 连通 图中一个节点的引用,请你返回该图的 深拷贝(克隆)。
图中的每个节点都包含它的值 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 。
输入:adjList = [[]]
输出:[[]]
解释:输入包含一个空列表。该图仅仅只有一个值为 1 的节点,它没有任何邻居。
输入:adjList = []
输出:[]
解释:这个图是空的,它不含任何节点。
输入:adjList = [[2],[1]]
输出:[[2],[1]]
1 )深度优先遍历
/**
* Definition for Node.
* class Node {
* val: number
* neighbors: Node[]
* constructor(val?: number, neighbors?: Node[]) {
* this.val = (val===undefined ? 0 : val)
* this.neighbors = (neighbors===undefined ? [] : neighbors)
* }
* }
*/
// 深度优先遍历方法
function cloneGraph(node: Node | null): Node | null {
if(!node) return;
const visited = new Map(); // 记录哪些节点被访问,以及节点的映射关系
const dfs = (n: Node | null) => {
// console.log(n.val);
let nCopy = new Node(n.val); // 克隆了一个节点
visited.set(n, nCopy); // 将每个拷贝的节点和之前的节点做一个映射的关系
// 空数组的forEach不会执行
(n.neighbors || []).forEach(ne => {
if(!visited.has(ne)) {
dfs(ne);
}
nCopy.neighbors.push(visited.get(ne));
});
};
dfs(node);
return visited.get(node); // 将起始节点的拷贝作为克隆图的引用返回
}
解题思路
解题步骤
时间复杂度:O(n)
空间复杂度:O(n)
2 )广度优先遍历
/**
* Definition for Node.
* class Node {
* val: number
* neighbors: Node[]
* constructor(val?: number, neighbors?: Node[]) {
* this.val = (val===undefined ? 0 : val)
* this.neighbors = (neighbors===undefined ? [] : neighbors)
* }
* }
*/
function cloneGraph(node: Node | null): Node | null {
if(!node) return;
const visited = new Map(); // 记录哪些节点被访问,以及节点的映射关系
// visited.set(node, true); // 标记第一个节点被访问过
visited.set(node, new Node(node.val)); // 克隆一个起始节点并和原始节点做关联
const q = [node];
while(q.length) {
const n = q.shift();
// console.log(n.val);
(n.neighbors || []).forEach(ne => {
if(!visited.has(ne)) {
q.push(ne);
visited.set(ne, new Node(ne.val)); // 拷贝节点
}
// 拷贝边
visited.get(n).neighbors.push(visited.get(ne));
})
}
return visited.get(node);
}