LeetCode - Clone Graph

Problem description

description

Given a reference of a node in a connected undirected graph.

Return a deep copy (clone) of the graph.

Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors.

class Node {
    public int val;
    public List<Node> neighbors;
}

Analysis

This is a standard BFS/DFS problem.

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;
    
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/

class Solution {
    public Node cloneGraph(Node node) {
        if (node == null){
            return node;
        }
        Node root = new Node(node.val);
        
        HashMap<Integer, Node> map = new HashMap<>();
        map.put(node.val, root);
        
        Queue<Node> q = new ArrayDeque<>();
        q.offer(node);
        
        HashSet<Integer> visited = new HashSet<>();
        
        while(!q.isEmpty()){
            int size = q.size();
            
            for (int i = 0; i < size; i++){
                Node n = q.poll();
                Node c = map.get(n.val);
                
                if (visited.contains(n.val)){
                    continue;
                }
                
                visited.add(n.val);
                
                for (Node nn:n.neighbors){
                    if (map.containsKey(nn.val)){
                        c.neighbors.add(map.get(nn.val));
                    }
                    else{
                        Node cp = new Node(nn.val);
                        c.neighbors.add(cp);
                        map.put(nn.val, cp);
                    }
                    
                    q.offer(nn);
                }
            }
        }
        
        return root;
    }
}

And DFS version:

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;

    public Node() {}

    public Node(int _val,List<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/
class Solution {
    private HashMap <Node, Node> visited = new HashMap <> ();
    public Node cloneGraph(Node node) {
        if (node == null) {
            return node;
        }

        // If the node was already visited before.
        // Return the clone from the visited dictionary.
        if (visited.containsKey(node)) {
            return visited.get(node);
        }

        // Create a clone for the given node.
        // Note that we don't have cloned neighbors as of now, hence [].
        Node cloneNode = new Node(node.val, new ArrayList());
        // The key is original node and value being the clone node.
        visited.put(node, cloneNode);

        // Iterate through the neighbors to generate their clones
        // and prepare a list of cloned neighbors to be added to the cloned node.
        for (Node neighbor: node.neighbors) {
            cloneNode.neighbors.add(cloneGraph(neighbor));
        }
        return cloneNode;
    }
}

What to improve