Clone Graph LeetCode solution in Java

1
/*
2
// Definition for a Node.
3
class Node {
4
    public int val;
5
    public List<Node> neighbors;
6
    public Node() {
7
        val = 0;
8
        neighbors = new ArrayList<Node>();
9
    }
10
    public Node(int _val) {
11
        val = _val;
12
        neighbors = new ArrayList<Node>();
13
    }
14
    public Node(int _val, ArrayList<Node> _neighbors) {
15
        val = _val;
16
        neighbors = _neighbors;
17
    }
18
}
19
*/
20

21
class Solution {
22
  public void dfs(Node node, Node copy, Node[] visited) {
23
    visited[copy.val] =
24
        copy; // store the current node at it's val index which will tell us that this node is now
25
    // visited
26

27
    //         now traverse for the adjacent nodes of root node
28
    for (Node n : node.neighbors) {
29
      //             check whether that node is visited or not
30
      //              if it is not visited, there must be null
31
      if (visited[n.val] == null) {
32
        //                 so now if it not visited, create a new node
33
        Node newNode = new Node(n.val);
34
        //                 add this node as the neighbor of the prev copied node
35
        copy.neighbors.add(newNode);
36
        //                 make dfs call for this unvisited node to discover whether it's adjacent
37
        // nodes are explored or not
38
        dfs(n, newNode, visited);
39
      } else {
40
        //                 if that node is already visited, retrieve that node from visited array
41
        // and add it as the adjacent node of prev copied node
42
        //                 THIS IS THE POINT WHY WE USED NODE[] INSTEAD OF BOOLEAN[] ARRAY
43
        copy.neighbors.add(visited[n.val]);
44
      }
45
    }
46
  }
47

48
  public Node cloneGraph(Node node) {
49
    if (node == null)
50
      return null; // if the actual node is empty there is nothing to copy, so return null
51
    Node copy =
52
        new Node(node.val); // create a new node , with same value as the root node(given node)
53
    Node[] visited =
54
        new Node
55
            [101]; // in this question we will create an array of Node(not boolean) why ? , because
56
    // i have to add all the adjacent nodes of particular vertex, whether it's
57
    // visited or not, so in the Node[] initially null is stored, if that node is
58
    // visited, we will store the respective node at the index, and can retrieve that
59
    // easily.
60
    Arrays.fill(visited, null); // initially store null at all places
61
    dfs(node, copy, visited); // make a dfs call for traversing all the vertices of the root node
62
    return copy; // in the end return the copy node
63
  }
64
}