133. Clone Graph

Approach 1: BFS

• Time: $O(|V| + |E|)$
• Space: $O(|V| + |E|)$

C++JavaPython

class Solution {
 public:
  Node* cloneGraph(Node* node) {
    if (node == nullptr)
      return nullptr;

    queue<Node*> q{{node}};
    unordered_map<Node*, Node*> map{{node, new Node(node->val)}};

    while (!q.empty()) {
      Node* u = q.front();
      q.pop();
      for (Node* v : u->neighbors) {
        if (!map.contains(v)) {
          map[v] = new Node(v->val);
          q.push(v);
        }
        map[u]->neighbors.push_back(map[v]);
      }
    }

    return map[node];
  }
};

class Solution {
  public Node cloneGraph(Node node) {
    if (node == null)
      return null;

    Queue<Node> q = new ArrayDeque<>(Arrays.asList(node));
    Map<Node, Node> map = new HashMap<>();
    map.put(node, new Node(node.val));

    while (!q.isEmpty()) {
      Node u = q.poll();
      for (Node v : u.neighbors) {
        if (!map.containsKey(v)) {
          map.put(v, new Node(v.val));
          q.offer(v);
        }
        map.get(u).neighbors.add(map.get(v));
      }
    }

    return map.get(node);
  }
}

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

    q = collections.deque([node])
    map = {node: Node(node.val)}

    while q:
      u = q.popleft()
      for v in u.neighbors:
        if v not in map:
          map[v] = Node(v.val)
          q.append(v)
        map[u].neighbors.append(map[v])

    return map[node]

Approach 2: DFS

• Time: $O(|V| + |E|)$
• Space: $O(|V| + |E|)$

C++JavaPython

class Solution {
 public:
  Node* cloneGraph(Node* node) {
    if (node == nullptr)
      return nullptr;
    if (const auto it = map.find(node); it != map.cend())
      return it->second;

    Node* newNode = new Node(node->val);
    map[node] = newNode;

    for (Node* neighbor : node->neighbors)
      newNode->neighbors.push_back(cloneGraph(neighbor));

    return newNode;
  }

 private:
  unordered_map<Node*, Node*> map;
};

class Solution {
  public Node cloneGraph(Node node) {
    if (node == null)
      return null;
    if (map.containsKey(node))
      return map.get(node);

    Node newNode = new Node(node.val);
    map.put(node, newNode);

    for (Node neighbor : node.neighbors)
      newNode.neighbors.add(cloneGraph(neighbor));

    return newNode;
  }

  private Map<Node, Node> map = new HashMap<>();
}

class Solution:
  def cloneGraph(self, node: 'Node') -> 'Node':
    if not node:
      return None
    if node in self.map:
      return self.map[node]

    newNode = Node(node.val, [])
    self.map[node] = newNode

    for neighbor in node.neighbors:
      self.map[node].neighbors.append(self.cloneGraph(neighbor))

    return newNode

  map = {}