0133-clone-graph.js

/**
 * https://leetcode.com/problems/clone-graph/
 * Time O(V + E) | Space O(N)
 * @param {Node} node
 * @return {Node}
 */
var cloneGraph = function (node, seen = new Map()) {
    const isBaseCase = node === null;
    if (isBaseCase) return null;

    if (seen.has(node)) return seen.get(node);

    return dfs(node, seen); /* Time O(V + E) | Space O(N) */
};

const dfs = (node, seen) => {
    const clone = new Node(node.val);

    seen.set(node, clone); /*               | Space O(N) */

    for (const neighbor of node.neighbors) {
        const cloneNeighbor = cloneGraph(
            neighbor,
            seen,
        ); /* Time O(V + E) | Space O(H) */

        clone.neighbors.push(
            cloneNeighbor,
        ); /*               | Space O(V + E) */
    }

    return clone;
};

/**
 * https://leetcode.com/problems/clone-graph/
 * Time O(V + E) | Space O(N)
 * @param {Node} node
 * @return {Node}
 */
var cloneGraph = function (node, seen = new Map()) {
    const isBaseCase = node === null;
    if (isBaseCase) return null;

    seen.set(node, new Node(node.val)); /*               | Space O(N) */

    bfs(new Queue([node]), seen); /* Time O(V + E) | Space O(N) */

    return seen.get(node);
};

const bfs = (queue, seen) => {
    while (!queue.isEmpty()) {
        /* Time O(V + E) */
        for (let i = queue.size() - 1; 0 <= i; i--) {
            /* Time O(W) */
            const node = queue.dequeue();

            cloneNeighbors(node, seen, queue); /* Space O(N) */
        }
    }
};

const cloneNeighbors = (node, seen, queue) => {
    for (const neighbor of node.neighbors) {
        if (!seen.has(neighbor)) {
            seen.set(neighbor, new Node(neighbor.val)); /* Space O(N) */
            queue.enqueue(neighbor); /* Space O(W) */
        }

        const [parentClone, neighborClone] = [
            seen.get(node),
            seen.get(neighbor),
        ];

        parentClone.neighbors.push(neighborClone); /* Space O(V + E) */
    }
};