LeetCode 133. 克隆图

题目描述

难度：Middle

相关话题：深度优先搜索、广度优先搜索、图

给定无向连通
图中一个节点的引用，返回该图的深拷贝
（克隆）。图中的每个节点都包含它的值 val （ Int ） 和其邻居的列表（ list[Node] ）。

示例：

输入：{"$id":"1","neighbors":[{"$id":"2","neighbors":[{"$ref":"1"},{"$id":"3","neighbors":[{"$ref":"2"},{"$id":"4","neighbors":[{"$ref":"3"},{"$ref":"1"}],"val":4}],"val":3}],"val":2},{"$ref":"4"}],"val":1}

解释：
节点 1 的值是 1，它有两个邻居：节点 2 和 4 。
节点 2 的值是 2，它有两个邻居：节点 1 和 3 。
节点 3 的值是 3，它有两个邻居：节点 2 和 4 。
节点 4 的值是 4，它有两个邻居：节点 1 和 3 。

提示：

1. 节点数介于 1 到 100 之间。

2. 无向图是一个简单图
   ，这意味着图中没有重复的边，也没有自环。

3. 由于图是无向的，如果节点 p 是节点 q 的邻居，那么节点 q 也必须是节点 p 的邻居。

4. 必须将给定节点的拷贝 作为对克隆图的引用返回。

---

思路：

这是一个带有环的图，因此hash必须在执行遍历neighbors之前保存当前的copy Node，这样后面如果遇到循环引用，也能引用到hash里的copy Node。

遍历neighbors并且填充copy Node.neighbors。

/**
 * @ Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * // Definition for a Node.
 * function Node(val,neighbors) {
 *    this.val = val;
 *    this.neighbors = neighbors;
 * };
 */
/**
 * @param {Node} node
 * @return {Node}
 */
var cloneGraph = function(node) {
  let hash={}
  function clone(node){
    let val=node.val,adj=node.neighbors
    if(hash[val])return hash[val]
    let copy=new Node(val,[])
    hash[val]=copy
    for(let i=0;i<adj.length;i++){
      copy.neighbors[i]=clone(adj[i])
    }
    return copy
  }
  return clone(node)

};