LeetCode 133. 克隆图
题目描述
✅ 133. 克隆图
题意分析
给定无向连通图中的一个节点，创建整张图的深拷贝，返回与输入节点对应的新节点。每个新节点的值与原节点相同，相邻关系也相同，但节点对象和邻接表都必须是新创建的，不能把原图对象混入结果。
同一个原节点无论从多少条路径到达，都只能对应同一个副本。多个原节点共享一个邻居时，它们的副本也必须共同指向那个邻居的同一份副本，而不是各自再复制一次。
输入节点为空时返回空；只有一个孤立节点时，也应创建一个值相同、邻接表为空的新节点。这里的返回值是图的入口，复制工作需要沿邻接关系覆盖所有可达节点。
解法：DFS + 原节点到克隆节点映射
核心思路
[!blue]
可以沿邻接关系做 DFS，但图与树不同，同一个节点可能通过多个邻居反复到达。无向边本身也会让递归从一个端点走到另一个端点后再次访问原端点，因此不能每遇到一个节点就无条件新建并继续递归。
用映射
clones记录“原节点对象 → 副本节点对象”。如果当前原节点已经登记，直接返回对应副本：既避免再次展开它的邻居，也保证所有指向该原节点的边最终都指向同一个新对象。第一次访问节点时，先创建只包含节点值、邻接表为空的副本，并立即放入映射，再处理邻居。这个先后顺序很关键：递归尚未填完副本的邻接表时，其他路径就可能重新访问当前节点，提前登记让它们可以拿到已分配的副本，而不再次递归。副本对象先确定，邻接内容随后逐步补齐，不要求返回已登记节点时它已经完全填好。
接着逐个递归克隆原邻居，将每次返回的新节点加入当前副本的邻接表。对每一条原邻接引用都建立一条对应的新引用，节点映射保持一一对应，便同时保留了节点值、边和共享关系。整个过程只读取原图，不修改原节点或原邻接表。
每个原节点只有第一次访问会创建副本并遍历邻居，后续访问直接复用映射；有限节点全部处理完后递归结束。入口为这次复制创建一张新的映射，避免不同复制调用之间复用旧图副本。
解题步骤
- 在入口创建空映射，调用递归函数处理输入节点。
- 当前节点为空时返回空；已存在映射时直接返回已有副本。
- 否则创建值相同、邻接表独立的新节点，并立即登记到映射中。
- 依次递归处理当前原节点的所有邻居，把返回的副本加入新节点邻接表。
- 返回当前副本；最外层得到的就是整张克隆图的入口。
代码实现
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)，其中V为节点数，E为无向边数。每个节点只创建和展开一次，每条无向边的两个邻接引用各处理一次，仍为线性总量。- 空间复杂度：辅助空间为
O(V)，包括映射和最坏深度为V的递归栈。返回的克隆图另需O(V + E)空间保存节点和邻接表。
关键点总结
[!green]
- 映射同时承担访问标记和副本定位，不只是记录一个节点是否见过。
- 先登记对象、再填充邻接表，才能处理往返访问以及尚未复制完成时的交叉引用。
- 每条新边都连接映射得到的新节点，保证没有原图引用残留。
- 多条路径复用同一副本，保留的是原图的共享结构，而不是把图展开成树。
易错点总结
[!yellow]
- 复制完邻居才登记映射：递归可能沿无向边返回正在处理的节点，找不到记录后继续展开，无法结束。
- 只用布尔值记录访问：再次访问时仍需要知道应该连接哪个副本，必须保存对象映射。
- 每条边都重新创建邻居：会把一个原节点拆成多个副本，破坏共享关系。
- 直接复制原邻接引用或复用原列表：结果仍依赖原图对象，只完成了浅拷贝。
- 只处理首次遇到的邻居关系：已经访问过的邻居无需再次展开，但仍需要把它的副本加入当前邻接表，否则会漏边。
- 没有判断空输入：应在读取节点值之前处理空节点，统一返回空。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 138. 随机链表的复制 | 中等 | 两题都先建立原节点到副本节点的映射再恢复引用；该题可利用链表 next 暂存映射，图的任意邻接关系则需要显式哈希表。 |