0%

Leetcode133

133. 克隆图

难度中等390收藏分享切换为英文接收动态反馈

给你无向 连通 图中一个节点的引用,请你返回该图的 深拷贝(克隆)。

图中的每个节点都包含它的值 valint) 和其邻居的列表(list[Node])。

Solution

dfs就可以解决

题目提供了索引就是val,所以map的key可以使用val来简化体积

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
/**
* // Definition for a Node.
* function Node(val, neighbors) {
* this.val = val === undefined ? 0 : val;
* this.neighbors = neighbors === undefined ? [] : neighbors;
* };
*/

/**
* @param {Node} node
* @return {Node}
*/
var cloneGraph = function (node) {
if (!node) return;
let isVisit = new Map();
//dfs
const dfs = function (item) {
const newNode = new Node(item.val);
isVisit.set(item.val, newNode);
// console.log('isVist===>',isVisit)
// deep clone
for (let neighbor of item.neighbors) {
if (!isVisit.has(neighbor.val)) {
dfs(neighbor);
}
newNode.neighbors.push(isVisit.get(neighbor.val))
}
}
dfs(node);
return isVisit.get(node.val);
};