133-clone-graph.js

/**
 *   - if(!node) return node. Graphs can also have null neighbors
 *   - using a Set doesn't work because we are dealing with objects not primitives
 *       - and when encountering an already-cloned node, you are supposed to return the copied node
 *       (otherwise you are linking back to the original)
 *       - so, map = {} is correct
 *   - the only "trick" is that you must set the current node as "already copied" before DFS-ing its neighbors
 *   - declaring new variable for copying a node is actually extra O(n) space
 */

/**
 * // Definition for a Node.
 * function Node(val,neighbors) {
 *    this.val = val;
 *    this.neighbors = neighbors;
 * };
 */
/**
 * @param {Node} node
 * @return {Node}
 */
const cloneGraph = function (node) {
  if (!node) return node;
  const map = {};
  return traverse(node);
  function traverse(node) {
    if (!node) return node;
    if (!map[node.val]) {
      const newNode = new Node(node.val);
      map[node.val] = newNode;
      newNode.neighbors = node.neighbors.map(traverse);
    }
    return map[node.val];
  }
};