LeetCode 133「克隆图」本质是给一张可能有环的无向连通图做深拷贝新节点必须全部“new” 出来邻居关系要和原图一一对应且不能引用原节点。核心套路就一句用“Map” 存「原节点 → 克隆节点」的映射首次见到原节点就建克隆并登记之后再遇到直接复用既能去重又能打断环。节点结构LeetCode JS 环境里一般是这样函数式构造function _Node(val, neighbors) {this.val val undefined ? 0 : val;this.neighbors neighbors undefined ? [] : neighbors;}✅ DFS 解法最常用/**param {_Node} nodereturn {_Node}*/var cloneGraph function (node) {if (!node) return null;const visited new Map(); // 原节点 - 克隆节点const dfs (cur) {// 已经克隆过直接返回if (visited.has(cur)) return visited.get(cur);// 先建克隆节点并登记必须在递归邻居之前 const clone new _Node(cur.val); visited.set(cur, clone); // 再递归克隆邻居 for (const nei of cur.neighbors) { clone.neighbors.push(dfs(nei)); } return clone;};return dfs(node);};为什么「先 set 再递归」不能反图里有环比如 1→2→1如果等递归完才往 Map 里放克隆 1 → 克隆 2 → 又回到 1 → Map 里还没有 1 的克隆 → 继续递归 → 死循环/栈溢出先“visited.set(cur, clone)” 再处理邻居回路回来时就能直接拿到已创建的 clone。✅ BFS 解法迭代无递归栈风险节点数 ≤100 时 DFS 完全够用图很深时用 BFS 更稳。var cloneGraph function (node) {if (!node) return null;const visited new Map();visited.set(node, new _Node(node.val));const queue [node];while (queue.length) {const cur queue.shift();const cloneCur visited.get(cur);for (const nei of cur.neighbors) { if (!visited.has(nei)) { visited.set(nei, new _Node(nei.val)); queue.push(nei); } // 把邻居的克隆挂到当前克隆节点上 cloneCur.neighbors.push(visited.get(nei)); }}return visited.get(node);};复杂度时间“O(V E)”每个节点访问一次每条边遍历一次空间“O(V)”Map 存所有克隆节点 递归栈或队列常见踩坑❌ 用“val” 当 Map 的 key虽然本题 val 唯一但通用做法是用节点对象本身当 key否则换到「值可重复」的图就错❌clone.neighbors node.neighbors这是浅拷贝把原节点引用塞进去了不是深拷贝❌ 忘了处理“node null”题目示例 3 会传空图❌ 克隆节点建完不先存 Map 就递归邻居 → 环图爆炸一句话记忆点克隆图 图遍历DFS/BFS 一张「原节点→新节点」的备忘录先建档再访邻需要我顺便把这道和 LeetCode 138「复制带随机指针的链表」放在一起对比下套路吗两者几乎是同一个模板。
元宝 LeetCode 133. 克隆图 JavaScript语言实现
LeetCode 133「克隆图」本质是给一张可能有环的无向连通图做深拷贝新节点必须全部“new” 出来邻居关系要和原图一一对应且不能引用原节点。核心套路就一句用“Map” 存「原节点 → 克隆节点」的映射首次见到原节点就建克隆并登记之后再遇到直接复用既能去重又能打断环。节点结构LeetCode JS 环境里一般是这样函数式构造function _Node(val, neighbors) {this.val val undefined ? 0 : val;this.neighbors neighbors undefined ? [] : neighbors;}✅ DFS 解法最常用/**param {_Node} nodereturn {_Node}*/var cloneGraph function (node) {if (!node) return null;const visited new Map(); // 原节点 - 克隆节点const dfs (cur) {// 已经克隆过直接返回if (visited.has(cur)) return visited.get(cur);// 先建克隆节点并登记必须在递归邻居之前 const clone new _Node(cur.val); visited.set(cur, clone); // 再递归克隆邻居 for (const nei of cur.neighbors) { clone.neighbors.push(dfs(nei)); } return clone;};return dfs(node);};为什么「先 set 再递归」不能反图里有环比如 1→2→1如果等递归完才往 Map 里放克隆 1 → 克隆 2 → 又回到 1 → Map 里还没有 1 的克隆 → 继续递归 → 死循环/栈溢出先“visited.set(cur, clone)” 再处理邻居回路回来时就能直接拿到已创建的 clone。✅ BFS 解法迭代无递归栈风险节点数 ≤100 时 DFS 完全够用图很深时用 BFS 更稳。var cloneGraph function (node) {if (!node) return null;const visited new Map();visited.set(node, new _Node(node.val));const queue [node];while (queue.length) {const cur queue.shift();const cloneCur visited.get(cur);for (const nei of cur.neighbors) { if (!visited.has(nei)) { visited.set(nei, new _Node(nei.val)); queue.push(nei); } // 把邻居的克隆挂到当前克隆节点上 cloneCur.neighbors.push(visited.get(nei)); }}return visited.get(node);};复杂度时间“O(V E)”每个节点访问一次每条边遍历一次空间“O(V)”Map 存所有克隆节点 递归栈或队列常见踩坑❌ 用“val” 当 Map 的 key虽然本题 val 唯一但通用做法是用节点对象本身当 key否则换到「值可重复」的图就错❌clone.neighbors node.neighbors这是浅拷贝把原节点引用塞进去了不是深拷贝❌ 忘了处理“node null”题目示例 3 会传空图❌ 克隆节点建完不先存 Map 就递归邻居 → 环图爆炸一句话记忆点克隆图 图遍历DFS/BFS 一张「原节点→新节点」的备忘录先建档再访邻需要我顺便把这道和 LeetCode 138「复制带随机指针的链表」放在一起对比下套路吗两者几乎是同一个模板。
