# 133. Clone Graph

{% embed url="<https://leetcode.com/problems/clone-graph/>" %}

## Solution

DFS  + Map to record

```
class Solution {
    public Node cloneGraph(Node node) {
        if(node == null) return null;
        HashMap<Integer, Node> map = new HashMap<>();
        return cloneGraph(node, map);
    }
    
    public Node cloneGraph(Node node, HashMap<Integer, Node> map){
        if(map.containsKey(node.val)){
            return map.get(node.val);
        }
        Node newNode = new Node(node.val);
        map.put(node.val, newNode);
        
        for(Node neighbor : node.neighbors){
            newNode.neighbors.add(cloneGraph(neighbor, map));
        }
        return newNode;   
    }
}
```
