LeetCode 133 Clone Graph迭代DFS解法节点不存在错误排查

代码错误原因 #

• 核心问题是你直接修改了原图的邻接表结构：你写的let nodeNeighbors = currentNode.neighbors;属于引用赋值，后续对nodeNeighbors调用shift()方法，本质是直接操作原节点的neighbors数组，把里面的元素逐个删除。LeetCode判题时会保留原图结构做校验，你修改原图后，后台校验逻辑找不到对应节点，就抛出了节点不存在的错误。
• 次要问题：你声明用的是迭代式DFS，但实际用stack.shift()从数组头部取元素，这是队列的先进先出逻辑，属于BFS的实现，如果要写DFS应该替换为stack.pop()从尾部取元素，不过这个问题不影响功能正确性，只是实现和预期不符。

修复方案 #

遍历原节点邻接表的时候不要修改原数组，用普通的遍历方法即可，修改后的代码如下：

/**
 * // 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) {
    return node;
  }
  const nodeCopy = new Node(node.val);
  let stack = [node];
  let nodeMap = {};
  nodeMap[node.val] = nodeCopy;
  while (stack.length > 0) {
    // 迭代DFS用pop，要写BFS可以换成shift
    const currentNode = stack.pop();
    const currentNodeCopy = nodeMap[currentNode.val];
    // 直接遍历邻接表，不修改原数组
    for (const currentNeighbor of currentNode.neighbors) {
      let existingNeighborCopy = nodeMap[currentNeighbor.val];
      if (!existingNeighborCopy) {
        stack.push(currentNeighbor);
        nodeMap[currentNeighbor.val] = new Node(currentNeighbor.val);
      }
      currentNodeCopy.neighbors.push(nodeMap[currentNeighbor.val]);
    }
  }
  return nodeMap[node.val];
};

内容的提问来源于stack exchange，提问作者Y M