讨论/《队列 & 栈》 - 克隆图/
《队列 & 栈》 - 克隆图
/**
 * @param {Node} node
 * @return {Node}
 * @description DFS迭代解法
 */
var cloneGraph = function (node) {
  if (!node) {
    return null;
  }
  const history = new Map();
  const stack = [node];
  let current = node;
  while (stack.length) {
     // 找准一条路一直走下去
    while (current && !history.has(current.val)) {
      let newNode = new Node(current.val);
      history.set(newNode.val, newNode);
      for (var i = 0; i < current.neighbors.length; i++) {
        if (!history.has(current.neighbors[i].val)) {
          current = current.neighbors[i];
          stack.push(current);
          break;
        }
      }
    }
    // 走到头开始回退
    current = stack.pop();
    let newCurrent = history.get(current.val);
    for (var i = 0; i < current.neighbors.length; i++) {
      if (!history.has(current.neighbors[i].val)) {
        let newNode = new Node(current.neighbors[i].val);
        history.set(newNode.val, newNode);
        newCurrent.neighbors.push(newNode);
        stack.push(current.neighbors[i]); // 回退过程中发现分岔路口,走进去
      } else {
        newCurrent.neighbors.push(history.get(current.neighbors[i].val));
      }
    }
  }
  return history.get(node.val);
};
展开全部 3 讨论