给你无向 连通 图中一个节点的引用,请你返回该图的 深拷贝(克隆)。
图中的每个节点都包含它的值 val(int) 和其邻居的列表(list[Node])。
思路
步骤
/** * @param {Node} node * @return {Node} */ var cloneGraph = function(node) { if(!node) return; const map = new Map() const bfs = (node) => { const nCopy = new Node(node.val); map.set(node, nCopy); (node.neighbors || []).forEach(n => { if(!map.has(n)) { bfs(n) } nCopy.neighbors.push(map.get(n)) }) } bfs(node) return map.get(node) };
时间复杂度:O(n)
空间复杂度:O(n)
var cloneGraph = function(node) { if(!node) return; const map = new Map() const q = [node] map.set(node, new Node(node.val)) while(q.length) { const n = q.shift(); (n.neighbors || []).forEach(c => { if(!map.has(c)) { q.push(c) map.set(c, new Node(c.val)) } map.get(n).neighbors.push(map.get(c)) }) } return map.get(node) };
时间复杂度:O(n)
空间复杂度:O(n)