Shinkai005
V1
2022/02/12阅读:29主题:红绯
【leetcode】133.克隆图
【leetcode】133.克隆图.md
==题目描述==
==题目思路==
-
拷贝所有节点 -
拷贝所有的边
==个人题解==
-
遍历所有的节点 -
拷贝所有节点存储起来 -
将拷贝的节点根据原图的方式进行链接
/**
* // 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) {
// 1. 遍历所有的节点
// 2. 拷贝所有节点存储起来
// 3. 将拷贝的节点根据原图的方式进行链接
if (!node) return;
// 用map主要是为了建立映射关系.n和nCopy 还有neighbor之间
const visited = new Map();
// 深度遍历
const dfs = (n) => {
const nCopy = new Node(n.val);
visited.set(n, nCopy);
// 这里判[],是为了不影响程序继续执行.
(n.neighbors || []).forEach(ne => {
if (!visited.has(ne)) {
dfs(ne);
}
//当前遍历的是n.neighbors, 加入到nCopy数组中.
// 这里需要注意,加入的是nCopy
nCopy.neighbors.push(visited.get(ne));
});
};
dfs(node);
return visited.get(node);
};
==总结优化==
下面是广度遍历
/**
* // 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;
const visited = new Map();
visited.set(node, new Node(node.val))
const q = [node];
while (q.length) {
const n = q.shift();
(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);
};
==时间复杂度(time complexity)==
O(n)
==空间复杂度(space complexity)==
O(n) map数据结构
-
为什么不看递归的空间复杂度呢?
-
如果两个结构前后排列,就返回更大的那个.
-
作者介绍
Shinkai005
V1
公众号:深海笔记Shinkai