Grokking #196

class Solution {

  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;
    }
  }

  // store visited node, and cloned node
  Map<Node, Node> visited;

  public Node cloneGraph(Node node) {
    if (node == null) {
      return null;
    }

    visited = new HashMap<Node, Node>();

    dfsClone(node);

    return visited.get(node);
  }

  private void dfsClone(Node at) {
    if (visited.containsKey(at)) {
      return;
    }

    // clone current node and store mapping
    Node cloned = new Node(at.val);
    visited.put(at, cloned);

    // explore all neighbor nodes and clone
    for (Node to : at.neighbors) {
      dfsClone(to);

      // add cloned of neighbour node to current node's neighbors
      cloned.neighbors.add(visited.get(to));
    }
  }
}