LeetCode 133. Clone Graph：DFS实现深拷贝未通过验证求助

题目描述 #

给定无向连通图中一个节点的引用，返回该图的深拷贝（deep copy）。
图中的每个节点包含一个整数（int）val和一个邻居节点列表（List[Node]）。

class Node {
    public int val;
    public List<Node> neighbors;
}

测试用例格式： #

为简化起见，每个节点的val与其索引（1-indexed）相同。例如，第一个节点val == 1，第二个节点val == 2，以此类推。

问题情况 #

我用DFS遍历实现深拷贝，但提交后未通过验证。尝试打印原节点和拷贝节点的值及内存地址对比，仍无法理解为何不满足题目要求。以下是我的Python实现（已注释测试用冗余代码）：

"""
# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
"""

from typing import Optional
class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        if not node:
            return 
        if not node.neighbors:
            return Node(node.val)
        

        ans = Node(node.val,[])
        visited = set()

        def dfs(node,copy):
            if not node or node.val in visited:
                return
            visited.add(node.val)
            neighbors = node.neighbors
            for neighbor in neighbors:
                deepcopy = Node(neighbor.val)
                copy.neighbors.append(deepcopy)

                dfs(neighbor,deepcopy)

        dfs(node,ans)
        
        # test = set()
        # def dfsTest(og,copy):
        #     if og in test:
        #         return 
            
        #     test.add(og)
        #     og_n = og.neighbors
        #     copy_n = copy.neighbors

        #     for o,c in zip(og_n,copy_n):
        #         print(o,c)  
        #         print(o.val,c.val)
        #         dfsTest(o,c)  
        
        # dfsTest(node,ans)
        return ans

错误原因分析 #

你的代码核心问题是重复创建同一节点的拷贝实例，没有复用已创建的节点，导致拷贝后的图结构与原图不符。比如原图中节点1和节点2互相连接，你的代码在处理节点1的邻居时创建了节点2的拷贝，而处理节点2的邻居时又会新建一个节点1的拷贝——这就导致拷贝图里存在两个不同的节点1，完全破坏了原图的连通关系。

你用visited集合只记录了节点的val是否被访问，但val只能标识节点值，无法关联到已经创建的拷贝节点。正确的做法是用字典映射原节点到对应的拷贝节点，确保每个原节点只被拷贝一次。

修正后的代码 #

"""
# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
"""

from typing import Optional
class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        if not node:
            return None
        
        # 字典存储原节点到拷贝节点的映射，确保每个节点只拷贝一次
        node_map = {}
        
        def dfs(current_node):
            # 如果当前节点已经拷贝过，直接返回拷贝后的节点
            if current_node in node_map:
                return node_map[current_node]
            # 创建当前节点的拷贝
            copy_node = Node(current_node.val)
            node_map[current_node] = copy_node
            # 递归处理所有邻居，将邻居的拷贝加入当前节点的邻居列表
            for neighbor in current_node.neighbors:
                copy_node.neighbors.append(dfs(neighbor))
            return copy_node
        
        return dfs(node)

内容的提问来源于stack exchange，提问作者Kang_the_Conqueror