克隆图
Clone Graph
本机进度仅保存在当前浏览器
题目描述
给你一个无向连通图中一个节点的引用，请你返回该图的深拷贝（克隆）。图中的每个节点都包含它的值 val 和其邻居的列表 neighbors。
示例：邻接表 [[2, 4], [1, 3], [2, 4], [1, 3]] 克隆后结构一致。
解题思路
- 图的克隆难点在"环"：直接递归会无限循环。用哈希表记录「原节点 -> 克隆节点」，兼作访问标记。
- DFS：当前节点不在表中就先创建克隆并登记（先登记再递归，防止成环时重复创建），再递归克隆邻居列表。
- BFS 版本用队列同样以映射表去重，两个方向都可以，重点是"先建映射再建边"。
参考实现
查看参考实现Python · 建议先自行作答
def cloneGraph(node):
if not node:
return None
clones = {} # 原节点 -> 克隆节点
def dfs(cur):
if cur in clones:
return clones[cur]
copy = Node(cur.val)
clones[cur] = copy # 先登记再递归，防止环内重复创建
for nb in cur.neighbors:
copy.neighbors.append(dfs(nb))
return copy
return dfs(node)