02-Clone-Graph.md

Clone Graph

Problem Link

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

---

Pattern

• DFS
• BFS
• Graph

---

Approach

Use a hash map to remember cloned nodes and recursively copy all neighbors.

---

Time Complexity

O(V + E)

Space Complexity

O(V)

---

Java Solution

import java.util.*;
class Solution {
    private Map<Node, Node> map = new HashMap<>();

    public Node cloneGraph(Node node) {
        if (node == null) return null;
        if (map.containsKey(node)) return map.get(node);
        Node copy = new Node(node.val, new ArrayList<>());
        map.put(node, copy);
        for (Node neighbor : node.neighbors) copy.neighbors.add(cloneGraph(neighbor));
        return copy;
    }
}