[LeetCode] 133. Clone Graph

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

Use DFS approach to copy the graph. Because node's value is the same as its index. Node value can be used as key to locate the copied node.

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

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        copies = {}
        
        def copy(node):
            if not node:
                return None
            
            if node.val in copies:
                return copies[node.val]
            
            copied = Node(node.val)
            copies[node.val] = copied
            
            for n in node.neighbors:
                copied.neighbors.append(copy(n))
            
            return copied
        
        return copy(node)