what is wrong with my clone graph code

无法正确clone graph. 错在哪里呢？返回的结果只会克隆一部分图，无法克隆全部。

1. class Solution:
   
2.     def cloneGraph(self, node: 'Node') -> 'Node':
   
3.         def dfs(node):
   
4.             if node in seen:
   
5.                 return
   
6.             seen[node] = Node(node.val, [])
   
7.             for nxt in node.neighbors:
   
8.                 seen[node].neighbors.append(Node(nxt.val, []))
   
9.                 dfs(nxt)
   
10.         seen = {}
    
11.         dfs(node)
    
12.         return seen[node]

复制代码

"seen"要记录从原图节点到克隆节点的映射，你的第二份代码改成这样就可以了：

1. class Solution:
   
2.     def cloneGraph(self, node: 'Node') -> 'Node':
   
3.         def dfs(node):
   
4.             if node in seen:
   
5.                 return seen[node]
   
6.             res = Node(node.val, [])
   
7.             seen[node] = res
   
8.             for nxt in node.neighbors:
   
9.                 res.neighbors.append(dfs(nxt))
   
10.             return res
    
11.         seen = {}
    
12.         return dfs(node) if node else None
    

复制代码

又写一个递归版本的，还是报错 “AttributeError: 'NoneType' object has no attribute 'neighbors'

1. class Solution:
   
2.     def cloneGraph(self, node: 'Node') -> 'Node':
   
3.         def dfs(node):
   
4.             if not node or node in seen:
   
5.                 return
   
6.             seen.add(node)
   
7.             res = Node(node.val, [])
   
8.             for nxt in node.neighbors:
   
9.                 res.neighbors.append(dfs(nxt))
   
10.             return res
    
11.         seen = set()
    
12.         return dfs(node)

复制代码

magicsets 发表于 2019/07/20 11:19:19
"seen"要记录从原图节点到克隆节点的映射，你的第二份代码改成这样就可以了：

[mw_shl_code=python,true]class Solution:
    def cloneGr...

哈哈，厉害！多谢多谢！🙏