购物车中没有产品。
133. 克隆图（中等）
Blind 75 › 133. 克隆图（中等） （第 2 章）
题目
给定一个无向连通图中某个节点的引用 node，返回整张图的深拷贝：新图的节点数、节点值、连接关系都和原图一致，但每个节点都是新建对象，新节点之间互相连接，绝不引用原图节点。
每个节点有两个字段：val（整数值）和 neighbors（邻居节点列表）。
为方便描述，下面用邻接表表示输入与输出；实际入参是一个 Node 引用。自造示例：
adjList = [[2,3],[1,3,4],[1,2],[2]] → 返回新图中值为 1 的节点引用。新图仍可用 [[2,3],[1,3,4],[1,2],[2]] 描述，但 4 个节点全部是新建对象：copy1 ≠ node1，且 copy1.neighbors 指向的是 copy2、copy3，而不是原图的 node2、node3。
| 原节点 | 值 | 原邻居 | 克隆节点 | 克隆邻居 |
|---|---|---|---|---|
| node1 | 1 | node2, node3 | copy1 | copy2, copy3 |
| node2 | 2 | node1, node3, node4 | copy2 | copy1, copy3, copy4 |
| node3 | 3 | node1, node2 | copy3 | copy1, copy2 |
| node4 | 4 | node2 | copy4 | copy2 |
约束：节点数 0 ~ 100；1 ≤ Node.val ≤ 100 且每个值唯一；没有重边，也没有自环；图是连通的；空图时 node 为 null。
思路
一句话：一边遍历原图，一边用哈希表记录「原节点 → 已克隆节点」，克隆过的节点直接复用。
最直白的做法是：遇到一个节点就 new 一个复制品，再递归复制它的每个邻居。这个方向是对的，但直接写会出两类问题：
- 环会导致死循环。 比如
1 ↔ 2，复制 1 时去复制 2，复制 2 时又去复制 1，永远停不下来。 - 共享邻居会被重复复制。 如果节点 3 同时是节点 1、2 的邻居，它可能被创建多次，最后得到的新图结构就错了。
关键观察：深拷贝只要求「每个原节点恰好对应一个新节点」，剩下的事情都是把邻居指针接到对应的新节点上。因此只要有一张 原节点 → 新节点 的映射，问题就变成一次普通的图遍历。
映射表同时承担两个作用：判重（每个原节点只克隆一次）和断环（再次遇到同一节点时直接返回它的克隆）。至于遍历顺序，DFS 和 BFS 都可以；核心规则都是：先登记当前节点，再处理邻居。
解法
这里用 DFS 实现：
- 若
node为空，直接返回null，对应空图。 - 若当前原节点已经在映射表中，说明它的克隆已建好，直接返回，避免环和重复创建。
- 否则新建一个只复制
val的节点，并立刻写入映射表。 - 遍历当前节点的每个邻居，递归得到「邻居的克隆」，追加到当前克隆节点的
neighbors。 - 返回当前克隆节点。
处理上面示例时，映射表从空开始逐步长成：
| 步骤 | 动作 | 映射表 |
|---|---|---|
| 1 | 克隆 node1 | node1 → copy1 |
| 2 | 克隆 node2 | node1 → copy1, node2 → copy2 |
| 3 | 克隆 node3 | nod本篇为付费内容您已阅读试读部分，购买后即可解锁全文。 ⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。 |
还没有评论，来说两句？