133.克隆图

链接：133.克隆图
难度：Medium
标签：深度优先搜索、广度优先搜索、图、哈希表
简介：给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。

题解 1 - typescript

• 编辑时间：2020-08-12
• 执行用时：104ms
• 内存消耗：40.1MB
• 编程语言：typescript
• 解法介绍：深度克隆。

/**
 * // 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 === null) return null;
  const cloned = new Map();
  return clone(node);
  function clone(node) {
    const val = node.val;
    if (cloned.has(val)) return cloned.get(val);
    const newNode = new Node(val);
    cloned.set(val, newNode);
    newNode.neighbors = node.neighbors.map(v => clone(v));
    return newNode;
  }
};

题解 2 - typescript

• 编辑时间：2021-10-25
• 执行用时：80ms
• 内存消耗：39.9MB
• 编程语言：typescript
• 解法介绍：dfs。

function cloneGraph(node: Node | null): Node | null {
  if (node === null) return null;
  const map = new Map<number, Node>();
  dfs(node);
  return map.get(node.val)!;
  function dfs(node: Node | null): void {
    if (node === null || map.has(node.val)) return;
    const cloneNode = new Node(node.val);
    map.set(node.val, cloneNode);
    node.neighbors.forEach(neighbor => {
      dfs(neighbor);
      cloneNode.neighbors.push(map.get(neighbor.val)!);
    });
  }
}