class Solution {
    public Node cloneGraph(Node node) {
        return cloneGraph(new HashMap<>(), node);
    }

    private Node cloneGraph(Map<Integer, Node> map, Node node) {
        if(node == null) {
            return null;
        }

        if (map.containsKey(node.val)) {
            return map.get(node.val);
        }

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

        for (int i = 0; i < node.neighbors.size(); i++) {
            Node neighborNode = node.neighbors.get(i);
            copy.neighbors.add(map.getOrDefault(neighborNode.val, cloneGraph(map, node.neighbors.get(i))));
        }

        return copy;
    }
}