LeetCode 133. 克隆图
目录
题目描述
✅ 133. 克隆图
题意分析
题目给出无向连通图中的一个节点引用，要求返回这张图的深拷贝。深拷贝的含义是：返回的图里每一个节点都必须是新建对象，节点值与原图一一对应，邻接关系也完全相同，但整张新图不能引用到任何一个原节点。换句话说，把原图全部改掉也不该影响拷贝出来的图。
约束里的信号有几个。图是无向的，意味着每条边在两端的邻接表里各出现一次，从 A 走到 B 之后必然还能从 B 走回 A。图是连通的，意味着从给定节点出发能到达所有节点，不需要额外扫描其它入口。节点数很小（百量级），所以递归深度可控，也不需要考虑性能上的花招。节点值互不相同且等于节点编号，这一点看似方便，但不该依赖——真正稳妥的做法是按节点引用而不是按值来建立对应关系。
最关键的隐含条件是：无向图必然含环。哪怕只有两个节点 A、B 相连，A 的邻居里有 B、B 的邻居里有 A，就已经构成一个长度为 2 的环。所以「顺着邻接表递归拷贝」这个朴素想法如果不加任何记录，会在 A 和 B 之间无限来回，直接栈溢出。
边界包括：输入节点为空（返回空）；图只有一个节点且没有邻居（返回一个邻接表为空的新节点）；节点数为 0 的空图；以及多个不同节点的邻接表都指向同一个节点，此时该节点只能被克隆一次，且所有引用必须指向同一个克隆对象。
解法：DFS + 原节点到克隆节点映射
核心思路
图可能有环，也可能多个节点共同指向同一节点。如果只沿邻接表递归创建新节点，遇到环会无限递归；即使没有环，也可能把同一节点复制多次，破坏图的连接关系。
用哈希表维护
原节点 -> 克隆节点的一一映射，它同时承担两项职责：记录已访问节点，避免环；复用已经创建的克隆，保持共享邻居关系。DFS 到一个未访问节点时，必须先创建克隆并写入映射，再递归处理邻居。这样即使邻居立刻沿环走回来，也能从映射中拿到当前克隆，而不会再次创建。
正确性不变量是：哈希表中的每个键都恰好对应一个克隆节点；处理完某个原节点后，它的克隆邻接表与原邻接表顺序一致，并全部指向邻居的克隆。
解题步骤
- 空图直接返回
null。- 若当前节点已经在映射中，直接返回对应克隆。
- 创建只含节点值的克隆，并立即加入映射。
- 依次递归克隆每个邻居，把结果加入克隆节点的邻接表。
- 返回当前克隆节点。
对环
1 -> 2 -> 1，克隆 1 时先登记映射；从 2 再访问 1，能直接复用已登记的克隆 1，因此递归会正常结束。
代码实现
import java.util.HashMap;
import java.util.Map;
class Solution {
public Node cloneGraph(Node node) {
return clone(node, new HashMap<>());
}
private Node clone(Node node, Map<Node, Node> clones) {
if (node == null) {
return null;
}
if (clones.containsKey(node)) {
return clones.get(node);
}
Node copy = new Node(node.val);
clones.put(node, copy);
for (Node neighbor : node.neighbors) {
copy.neighbors.add(clone(neighbor, clones));
}
return copy;
}
}
func cloneGraph(node *Node) *Node {
return cloneNode(node, make(map[*Node]*Node))
}
func cloneNode(node *Node, clones map[*Node]*Node) *Node {
if node == nil {
return nil
}
if copy, ok := clones[node]; ok {
return copy
}
copy := &Node{Val: node.Val, Neighbors: make([]*Node, 0, len(node.Neighbors))}
clones[node] = copy
for _, neighbor := range node.Neighbors {
copy.Neighbors = append(copy.Neighbors, cloneNode(neighbor, clones))
}
return copy
}
复杂度分析
- 时间复杂度：$O(V+E)$，每个节点创建一次，每条邻接关系处理一次。
- 空间复杂度：$O(V)$，映射保存所有节点；最坏情况下递归栈也为 $O(V)$。
关键点总结
- 哈希表既是访问标记，也是原节点与克隆节点的映射。
- 一定要先登记克隆，再递归邻居，这是切断环的关键。
- 映射键必须使用节点身份，而不是节点值；不同节点可能具有相同值。
- 深拷贝后的所有邻接指针都必须指向克隆节点，不能混入原节点。
易错点总结
- 递归完邻居才写入映射，遇到自环或普通环会无限递归。
- 只用
val作为映射键，在节点值不唯一的通用图中会错误合并节点。- 把原邻居直接加入
copy.neighbors只是浅拷贝，修改原图仍会影响结果。- 只处理树形父子关系而不检查已访问节点，无法处理回边和共享邻居。
- 忘记空图判断会在读取
node.val时触发空指针错误。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 1490. 克隆 N 叉树 | 中等 | 无环结构的深拷贝 |
| 138. 随机链表的复制 | 中等 | 旧对象到新对象的映射 |
| 690. 员工的重要性 | 中等 | 按 id 索引的图上遍历 |
| 200. 岛屿数量 | 中等 | 网格图的访问标记 |
| 207. 课程表 | 中等 | 有向图判环 |
| 297. 二叉树的序列化与反序列化 | 困难 | 结构的序列化重建 |