python实现leetcode之133. 克隆图

解题思路

使用缓存记住已经计算过的，避免同一个对象拷贝多次
然后递归处理邻接节点
最后返回入口节点

133. 克隆图

代码

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val = 0, neighbors = []):
        self.val = val
        self.neighbors = neighbors
"""

class Solution(object):
    def __init__(self):
        self.cache = {}
    
    def cloneGraph(self, node):
        """
        :type node: Node
        :rtype: Node
        """
        if not node: return None
        if node.val not in self.cache:
            self.cache[node.val] = Node(val=node.val)
            neighbors = []
            for nb in node.neighbors:
                clone_nb = self.cloneGraph(nb)
                neighbors.append(clone_nb)
            self.cache[node.val].neighbors = neighbors
        return self.cache[node.val]