LeetCode 133 克隆图 是一道经典的 图遍历 深拷贝 问题。题目描述给你无向连通图中一个节点的引用请你返回该图的深拷贝克隆。图中的每个节点包含一个整数值“val” 和一个邻居列表“neighbors”。图中节点数在“[0, 100]” 之间。解题思路由于图可能存在环比如节点 A 的邻居是 BB 的邻居又是 A直接递归或遍历会导致无限循环。因此我们需要一个 哈希表字典 来记录原节点 - 克隆节点的映射关系如果节点已经克隆过直接返回克隆节点的引用。如果没克隆过创建新节点并递归/BFS 克隆其邻居。方法一DFS深度优先搜索递归Definition for a Node.class Node:definit(self, val 0, neighbors None):self.val valself.neighbors neighbors if neighbors is not None else []class Solution:def cloneGraph(self, node: ‘Node’) - ‘Node’:if not node:return None# 字典原节点 - 克隆节点 visited {} def dfs(cur_node): # 如果已经克隆过直接返回克隆节点 if cur_node in visited: return visited[cur_node] # 创建新节点注意先不克隆邻居避免递归死循环 clone_node Node(cur_node.val, []) visited[cur_node] clone_node # 递归克隆所有邻居 for neighbor in cur_node.neighbors: clone_node.neighbors.append(dfs(neighbor)) return clone_node return dfs(node)方法二BFS广度优先搜索迭代Definition for a Node.class Node:definit(self, val 0, neighbors None):self.val valself.neighbors neighbors if neighbors is not None else []from collections import dequeclass Solution:def cloneGraph(self, node: ‘Node’) - ‘Node’:if not node:return Nonevisited {} # 克隆起始节点 clone_node Node(node.val, []) visited[node] clone_node # 队列用于 BFS queue deque([node]) while queue: cur queue.popleft() # 遍历当前节点的所有邻居 for neighbor in cur.neighbors: if neighbor not in visited: # 如果邻居没被克隆过创建并加入队列 visited[neighbor] Node(neighbor.val, []) queue.append(neighbor) # 将邻居的克隆节点加入当前节点克隆体的 neighbors 列表 visited[cur].neighbors.append(visited[neighbor]) return clone_node复杂度分析时间复杂度“O(N)”其中“N” 是图中节点的数量。每个节点和每条边最多被访问一次。空间复杂度“O(N)”哈希表“visited” 需要存储所有节点的映射递归栈或队列在最坏情况下图退化为链表也需要“O(N)” 的空间。两种方法的对比方法 优点 适用场景DFS 代码简洁逻辑直观 图深度不大避免递归栈溢出BFS 无递归栈溢出风险 图深度很大时更安全如果你需要我帮你把这段代码改成 JavaScript 版本或者想看 LeetCode 138复制带随机指针的链表 的类似解法随时告诉我
