克隆图

克隆图

三月 06, 2022

克隆图

这道题我们需要用深度优先搜索来通过给定节点进行图的遍历，然后再拿一个dict去记录访问过的点就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    visited = {}
    def cloneGraph(self, node: 'Node') -> 'Node':
        if node == None:
            return node
        #如果节点为空直接返回
        if node in self.visited:
            return self.visited[node]
        #如果节点被访问则返回被访问的节点
        cloneNode = Node(node.val)
        #储存已经访问过的节点
        self.visited[node] = cloneNode
        #更新克隆节点的邻居
        for neighbor in node.neighbors:
            cloneNode.neighbors.append(self.cloneGraph(neighbor))
        return cloneNode

alt