133. Clone Graph

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

solution

• bfs

class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        if not node:
            return node

        node_dict = {}
        node_dict[node.val] = Node(node.val)  # 遍历copy时，快速定位已有Node, 用于neighbor关系。顺便记录了已遍历过的
        queue = collections.deque([node])

        while queue:
            cur = queue.popleft()  # 注意这里不能和node重名, 用于最后输出

            for neighbour in cur.neighbors:
                if neighbour.val not in node_dict:
                    node_dict[neighbour.val] = Node(neighbour.val)
                    queue.append(neighbour)  # 注意: 放在if里避免了重复遍历相同，因此没有创建额外的visited

                # 这里每次append, 而不是一个层之后 neighbor=clone_neighbor
                node_dict[cur.val].neighbors.append(node_dict[neighbour.val])

        return node_dict[node.val]

时间复杂度：O(V+E) 空间复杂度：O(V+E)

• dfs

class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        visited = defaultdict(Node)

        def clone(node):
            if not node:
                return
            
            if node in visited:
                return visited[node]
            
            clone_node = Node(node.val)
            visited[node] = clone_node

            for nei in node.neighbors:
                clone_node.neighbors.append(clone(nei))
            return clone_node
        
        return clone(node)

follow up

138. Copy List with Random Pointer

# 第一遍生成copy的node生成记录hash指向；第二遍把next和random point指向关联

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:  # 注意空
          return

        mydict = {}  # 关键是记录original到clone的关系，
        cur = head  # 后续还需要用到head
        while cur:
            mydict[cur] = Node(cur.val)
            cur = cur.next

        cur = head
        while cur:
            mydict[cur].next = mydict.get(cur.next, None)  # next和random都可能为None, 因此都用get
            mydict[cur].random = mydict.get(cur.random, None)
            cur = cur.next

        return mydict[head]

时间复杂度：O(n) 空间复杂度：O(n)

• 不使用hashmap, O(1)空间复杂度

# 首先把clone node链接到原有链表，再拷贝random节点引用

class Solution:
    def copyRandomList(self, head):
        node = head
        while node:
            copy = Node(node.label)
            next = node.next
            node.next = copy
            copy.next = next
            node = next
            
        node = head
        head2 = node.next
        while node:
            copy = node.next
            next = copy.next
            if next:
                copy.next = next.next
            if node.random:
                copy.random = node.random.next
            node = next
            
        return head2

1490. Clone N-ary Tree

1485 Clone Binary Tree With Random Pointer