133. Clone Graph

# Medium

刚看这道题有点不明白难点在哪，也不知道从何下手。

难点：你想克隆的节点的neigbors可能还不存在，所以要用一个hashmap存储所有已经克隆好的节点{node: cloneNode}. 如果邻居中有的节点还不存在，则用递归的方法去新建一个节点。需要一个helper函数帮忙，即建立一个节点。如果要克隆的这个节点已经存在了，即返回这个节点。

优点：每个节点的value都是唯一的，所以能使用hashMap

这属于DFS遍历

"""
# 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':
        dic = {}
        return self.helper(node, dic)
    
    def helper(self, node, dic):
        if node == None:
            return None
        if node in dic:
            return dic[node]
        
        clone = Node(node.val)
        dic[node] = clone
        for neighbor in node.neighbors:
            clone.neighbors.append(self.helper(neighbor, dic))
            
        return clone

BFS. 遍历queue里所有的点，如果neighbor不存在，就新建一个空的节点，并且添加到queue和原点-克隆点一一映射的hashMap里，每次从queue里出来就给它添加所有的neighbors。节点的connection慢慢补充齐全。因为只用了while循环，相比于DFS，更加高效一些。

"""
# 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':
        # edge case
        if node == None:
            return None
        
        
        dic = {}
        queue = [node]
        clone = Node(node.val)
        dic[node] = clone   # no any connections, independent start node
        
        while len(queue) != 0:
            node = queue.pop(0)
            for neighbor in node.neighbors:
                if neighbor not in dic:
                    dic[neighbor] = Node(neighbor.val)
                    queue.append(neighbor)
                dic[node].neighbors.append(dic[neighbor])
                
        return clone

觉得还是没有完全理解为什么这样做可以。