[LeetCode] Clone Graph

 

 

Problem

 

 

---

 

Iterative Solution

Things to do:

1. visit every node

2. copy all elements in neighbor

 

Time Complexity

O(N+M), where N is the number of nodes and M is the number of edges

 

 

Space Complexity

O(N)

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

class Solution(object):
    def cloneGraph(self, node):
        """
        :type node: Node
        :rtype: Node
        """
        # DFS
        # can't mark visited on the node, so make a dict that keeps
        # track of the visited nodes so far.
        # Value is the clone of the original node.
        if not node:
            return node
        
        stack = [node]
        visited = {node: Node(node.val)}
        while stack:
            curr = stack.pop()
            for n in curr.neighbors:
                if n not in visited:
                    stack.append(n)
                    visited[n] = Node(n.val)
                visited[curr].neighbors.append(visited[n])
        return visited[node]

 

Recursive Solution

 

 

Time Complexity

O(N+M), where N is the number of nodes and M is the number of edges

 

 

Space Complexity

O(N)

 

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

class Solution(object):
    def cloneGraph(self, node):
        """
        :type node: Node
        :rtype: Node
        """
        if not node:
            return node
        
        visited = {node: Node(node.val)}
        self.traverse(node, visited)
        return visited[node]
        
    def traverse(self, curr, visited):
        for n in curr.neighbors:
            if n not in visited:
                visited[n] = Node(n.val)
                self.traverse(n, visited)
            visited[curr].neighbors.append(visited[n])