建设自己网站,设计公司500强排名,网络营销课程目录,温州网站优化推广方案leetcode 133. 克隆图 给你无向 连通 图中一个节点的引用#xff0c;请你返回该图的 深拷贝#xff08;克隆#xff09;。
图中的每个节点都包含它的值 val#xff08;int#xff09; 和其邻居的列表#xff08;list[Node]#xff09;。
class Node { public int val;…leetcode 133. 克隆图 给你无向 连通 图中一个节点的引用请你返回该图的 深拷贝克隆。
图中的每个节点都包含它的值 valint 和其邻居的列表list[Node]。
class Node { public int val; public List neighbors; }
测试用例格式 简单起见每个节点的值都和它的索引相同。例如第一个节点值为 1val 1第二个节点值为 2val 2以此类推。该图在测试用例中使用邻接列表表示。 邻接列表 是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。 给定节点将始终是图中的第一个节点值为 1。你必须将 给定节点的拷贝 作为对克隆图的引用返回。
示例 1 输入adjList [[2,4],[1,3],[2,4],[1,3]] 输出[[2,4],[1,3],[2,4],[1,3]] 解释 图中有 4 个节点。 节点 1 的值是 1它有两个邻居节点 2 和 4 。 节点 2 的值是 2它有两个邻居节点 1 和 3 。 节点 3 的值是 3它有两个邻居节点 2 和 4 。 节点 4 的值是 4它有两个邻居节点 1 和 3 。
示例 2 输入adjList [[]] 输出[[]] 解释输入包含一个空列表。该图仅仅只有一个值为 1 的节点它没有任何邻居。
示例 3 输入adjList [] 输出[] 解释这个图是空的它不含任何节点。
示例 4 输入adjList [[2],[1]] 输出[[2],[1]] 提示
节点数不超过 100 。 每个节点值 Node.val 都是唯一的1 Node.val 100。 无向图是一个简单图这意味着图中没有重复的边也没有自环。 由于图是无向的如果节点 p 是节点 q 的邻居那么节点 q 也必须是节点 p 的邻居。 图是连通图你可以从给定节点访问到所有节点。 题目链接在链接 思路可以采用广度优先遍历或深度优先遍历的思路来做注意记录下已经访问过的节点 # Definition for a Node.
class Node:def __init__(self, val 0, neighbors None):self.val valself.neighbors neighbors if neighbors is not None else []import collections
class Solution:def cloneGraph(self, node: Node) - Node:if node None:return Noneq collections.deque()q.append(node)visited dict()newNode Node(node.val)visited[newNode.val] newNodewhile len(q) 0:len_q len(q) for i in range(len_q):top q.popleft()newNode visited[top.val]neighs []for x in top.neighbors:tmp Noneif x.val in visited:tmp visited[x.val]else:tmp Node(x.val)q.append(x) ## 没有遍历过才加入队列visited[x.val] tmpneighs.append(tmp)if len(neighs) 0:newNode.neighbors neighsreturn visited[node.val]
