Leetcode 133.克隆图：DFS 深拷贝没有被接受

Question

https://leetcode.com/problems/clone-graph/

沿途使用DFS遍历进行深度复制，但没有被接受。我尝试并排打印原始和副本的节点值及其内存地址，我似乎无法理解为什么我的深度复制不能作为工作解决方案通过。我注释掉了测试中不必要的行。

"""
# 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

Answer 1

问题是您的代码无法生成有循环的图。然而，这必须得到支持，因为输入图可以有循环，并且对于那些测试用例，您的代码将失败。

它为邻居创建一个新节点（

deepcopy

），即使该邻居已经被访问过。在这种情况下，您已经为（邻居）节点创建了一个副本，此时您应该重用它，而不是创建另一个副本。

为了实现这一目标，我建议将

visited

转换为字典，这样当节点已被访问时，您还可以检索为其创建的副本。

无关言论

• 我不会为

  dfs

  使用第二个参数。相反，让它返回复制的节点。
• 无需处理空输入图或与其他图有任何不同的单节点图：

  dfs

  会很好地处理这些。

更正

这是对实现该想法的代码的更正：

class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        visited = {}  # not a set, but a dict

        def dfs(node):
            if not node:
                return
            if node.val in visited:  # already visited
                return visited[node.val]  # get the copy we already created for it
            copy = Node(node.val)
            visited[node.val] = copy  # remember the copy we created for this node
            for neighbor in node.neighbors:
                deepcopy = dfs(neighbor)
                copy.neighbors.append(deepcopy)
            return copy

        return dfs(node)