BFS 需要用一个字典，记录原始节点和复制节点的对应关系。
队列里放原始节点如果不在字典中，需要把节点放入队列代码如下： 循环版本
""" # Definition for a Node. class Node(object): def __init__(self, val, neighbors): self.val = val self.neighbors = neighbors """ class Solution(object): def cloneGraph(self, node): """ :type node: Node :rtype: Node """ if node == None: return None memo = {} qu = [node] res = Node(node.val, []) memo[node] = res while qu: node = qu.pop(0) for i in node.neighbors: if i not in memo: p = Node(i.val, []) memo[i] = p qu.append(i) memo[node].neighbors.append(memo[i]) return res再来一个递归版本
class Solution(object): def cloneGraph(self, node): """ :type node: Node :rtype: Node """ self.memo = {} return self.clone(node) def clone(self, node): if node == None: return None if node in self.memo: return self.memo[node] p = Node(node.val, []) self.memo[node] = p for i in node.neighbors: p.neighbors.append(self.clone(i)) return p