题目：给定一个无向连通图中节点的引用，返回该图的深层副本（克隆）。图中的每个节点都包含它的值val(Int)和它的邻居列表(list[Node])。给定连接无向图中节点的引用，返回该图的深层副本（克隆）。图中的每个节点都包含一个val(int)和一个其邻居的列表(List[Node])。示例：输入：{"$id":"1","neighbors":[{"$id":"2","neighbors":[{"$ref":"1"},{"$id":"3","邻居":[{"$ref":"2"},{"$id":"4","邻居":[{"$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到100之间。无向图是一个简单的图，这意味着没有重复的边并且图中没有自环。由于图是无向的，如果节点p是节点q的邻居，则节点q也必须是节点p的邻居。必须返回给定节点的副本作为对克隆图的引用。注意：节点数会在1到100之间。无向图是一个简单的图#Simple_graph)，意思是图中没有重复的边，也没有自环。由于图是无向的，如果节点p有节点q作为邻居，那么节点q也必须有节点p作为邻居。您必须返回给定节点的副本作为对克隆图的引用。解题思路：涉及到图的遍历无非就是DFS（深度优先搜索）、BFS（广度优先搜索），前几天可以看看这篇文章：BFS需要借助队列来实现,DFS可以借助栈实现，也可以直接用递归实现。就这道题而言，直接用递归比较好，不用开辟额外的数据结构空间来记录节点。BFS和DFS的写法比较固定。建议花点时间了解一下，一劳永逸。这道题思路很清晰。关键是如何深拷贝随机节点。关于链表可以参考这篇文章：LeetCode138:Copyalinkedlistwithrandompointers。CopyListwithRandomPointer链表是线性的，可以将节点复制到每个节点之后，很巧妙的完成了深复制。显然，这种方法不能用于图这样的树结构，复制的节点只能借助数据结构来记录。这种新旧节点之间的映射，自然就是哈希表（字典）。Java:classSolution{publicNodecloneGraph(Nodenode){if(node==null)returnnode;Queuequeue=newLinkedList<>();//使用队列实现BFSMapmap=newHashMap<>();//HashmapNodehead=newNode(node.val,newArrayList<>());//头节点map.put(node,head);//哈希映射原节点和新节点queue.add(node);//原节点加入队列while(!queue.isEmpty()){//如果队列不为空则重复队列Nodetmp=queue.poll();//弹出队头Nodefor(Noden:tmp.neighbors){//遍历邻居节点if(!map.containsKey(n)){//当字典的key不包含节点时map.put(n,newNode(n.val,newArrayList<>()));//新增映射关系到字典queue.add(n);//加入队列}map.get(tmp).neighbors.add(map.get(n));//加入邻居节点}}returnhead;}}Python3:classSolution:defcloneGraph(self,node:'Node')->'Node':如果不是node:returnnodehead=Node(node.val,[])#头节点map={node:head}#初始化字典，建立新老节点映射关系queue=collections.deque()#queuequeue.append(node)#原节点加入队列whilequeue:#queuenotEmptytmp=queue.popleft()#弹出队列头节点fornintmp.neighbors:#traverseneighborsnodesifninmap.keys():#map[tmp].neighborswhennnodes存在于字典的键中.append(map[n])#直接添加到新节点的邻居节点else:map[n]=Node(n.val,[])#创建一个新节点并建立一个mappingrelationshipmap[tmp].neighbors.append(map[n])#从新的映射关系中取出节点加入邻居节点。在函数外定义字典Java:classSolution{Mapmap=newHashMap();publicNodecloneGraph(Nodenode){if(node==null)returnnode;map.put(node,newNode(node.val,newArrayList<>()));//每次都需要新建一个节点，并为(Noden:node.neighbors)建立映射关系{if(map.containsKey(n))map.get(node).neighbors.add(map.get(n));否则map.get(node).neighbors.add(cloneGraph(n));}返回map.get(节点);}}Python3:classSolution:map=dict()defcloneGraph(self,node:'Node')->'Node':如果不是节点：返回节点self.map[node]=Node(node.val,[])forninnode.neighbors:ifninself.map.keys():self.map[node].neighbors.append(self.map[n])else:self.map[node].neighbors.append(self.cloneGraph(n))returnself.map[node]注意:python中的字典取值时可以使用dict().get(key)或者dict[key]。时间复杂度为1，但是做算法题一定要用dict[key]。因为get()方法的效果是一样的，但是重复调用函数带来的时间消耗非常高。python语言天生就慢，所以应该养成尽可能优化代码的习惯。欢迎关注微信。新工。公众号：爱写Bug
