133. Clone Graph

LeetCode - The World's Leading Online Programming Learning PlatformLeetCode

DFS

/**
 * @param {Node} node
 * @return {Node}
 */

let m;
var cloneGraph = function (node) {
    if (node === null) 
        return null;
    
    m = new Map();
    return dfs(node);
};

function dfs(node) {

    if (m.get(node.val) !== undefined) 
        return m.get(node.val);
    
    const cloned = new Node(node.val, []);
    m.set(node.val, cloned);
    
    for (const there of node.neighbors) {
        cloned.neighbors.push(dfs(there));
    }

    return cloned;
}
Console

Iteration

time: O(n)

space: O(n)

/**
 * // Definition for a Node.
 * function Node(val, neighbors) {
 *    this.val = val === undefined ? 0 : val;
 *    this.neighbors = neighbors === undefined ? [] : neighbors;
 * };
 */

/**
 * @param {Node} node
 * @return {Node}
 */
var cloneGraph = function (node) {
    if (node === null) return null;

    const m = {};
    const visited = new Set();

    const q = [node];
    while (q.length > 0) {
        const here = q.shift();

        if (visited.has(here.val)) continue;
        
        m[here.val] = m[here.val] ?? new Node(here.val, []);

        for (const there of here.neighbors) {
            m[there.val] = m[there.val] ?? new Node(there.val, []); 
            m[here.val].neighbors.push(m[there.val]);
            q.push(there);
        }

        visited.add(here.val);
    }

    return m[node.val];
};