CloneGraphDFSUsingRecursion.java

public Node cloneGraphDFSWithRecursion(Node node) {
    if (node == null) {
        return node;
    }
    Map<Node, Node> lookup = new HashMap<>();
    return this.cloneGraphHelper(node, lookup);
}

/**
 * A dfs helper using recursion to make a copy of each node recursively via neighbors
 * @param node
 * @param lookup
 * @return the copied node of Node
 */
private Node cloneGraphHelper(Node node, Map<Node, Node> lookup) {
    if (node == null) {
        return node;
    }

    if (lookup.containsKey(node)) {
        return lookup.get(node);
    }

    Node copiedNode = new Node(node.val, new ArrayList<>());
    lookup.put(node, copiedNode);
    for (Node n : node.neighbors) {
        Node copiedN = this.cloneGraphHelper(n, lookup);
        copiedNode.neighbors.add(copiedN);
    }
    return copiedNode;
}