LeetCode 133

副标题 / 摘要 Clone Graph 不是单纯的图遍历题，而是“带环对象图的深拷贝”题。真正的关键不是能不能走完图，而是如何保证每个原节点只克隆一次，并且所有边都指向克隆图中的新节点。 预计阅读时长：12~15 分钟 标签：图、DFS、BFS、哈希表、深拷贝 SEO 关键词：克隆图, Clone Graph, 图深拷贝, LeetCode 133, DFS, BFS 元描述：通过“原节点 -> 新节点”映射表实现无向图深拷贝，讲清 DFS/BFS、环处理、复杂度与多语言代码。 目标读者 刷 LeetCode 图论题、希望掌握“深拷贝 + visited/map”模板的学习者 需要复制对象图、工作流图、拓扑结构的工程师 经常在“图遍历”和“对象复制”之间混淆的开发者 背景 / 动机 很多同学第一次做这题，会把它当成普通遍历题： DFS 一遍 BFS 一遍 把值抄过去 但真正难点在于： 图里可能有环 同一个节点可能从多条路径访问到 复制出来的新图，所有邻居必须指向“新节点”，不能混入旧节点引用 所以这题本质上是： 带环对象图的深拷贝问题 这类模式在工程里也很常见： 复制流程编排图 克隆编辑器里的节点网络 复制依赖关系图做快照 核心概念 深拷贝：返回的新图里每个节点都必须是新建对象 节点身份：判断“是不是同一个节点”看的是对象身份 / 引用，不只是 val 邻接关系保持：新图的边结构必须与原图完全一致 映射表：原节点 -> 克隆节点，既防止死循环，也防止重复创建 A — Algorithm（题目与算法） 题目重述 给定一个无向连通图中某个节点 node 的引用，请返回这个图的深拷贝。 每个节点结构如下： class Node { public int val; public List<Node> neighbors; } 题目测试用例使用邻接表表示图。 如果图不为空，给定节点总是值为 1 的节点。 ...