133. 克隆图

LeetCode

注意： 执行测试用例的时候，不会每次都在一个新的全局作用域中执行，需要注意变量的声明位置，防止污染代码执行

第一步 实现图的深度遍历 DFS

const cloneGraph = (node)=>{
  if(!node) return node;
  const dfs = (node) => {
    console.log(node.val);
    node.isVisit = true;
    node.neighbors.forEach(n => {
        if(!n.isVisit) dfs(n);
    });
  }
  dfs(node);
}

第二步 克隆节点并保存

const cloneGraph = (node)=>{
  if(!node) return node;
  const map = new Map();
  const dfs = (node) => {
    map.set(node,new Node(node.val))
    node.neighbors.forEach(n => {
      if(!map.get(n)) dfs(n);
    });
  }
  dfs(node);
}

第三步 添加节点间关系

const cloneGraph = (node)=>{
  if(!node) return node;
  const map = new Map();
  const dfs = (node) => {
    map.set(node,new Node(node.val))
    node.neighbors.forEach(n => {
      if(!map.get(n)) dfs(n);
      map.get(node).neighbors.push(map.get(n));
    });
  }
  dfs(node);
  return map.get(node)
}

变形写法

在传参的过程中添加更多的信息

var cloneGraph = function (node) {
  const map = new Map();
  const cloneNode = new Node(node.val);
  map.set(node.val, cloneNode)
  const dfs = (cloneNode, node, neighbors) => {
    for (let n of node.neighbors) {
      if (map.has(n.val)) {
        neighbors.push(map.get(n.val))
      } else {
        const cloneNode = new Node(n.val)
        neighbors.push(cloneNode)
        map.set(n.val, cloneNode)
        dfs(cloneNode, n, cloneNode.neighbors)
      }
    }
  }
  dfs(cloneNode, node, cloneNode.neighbors)
  return cloneNode;
};

广度优先遍历BFS

const cloneGraph = (node) => {
  if (!node) return node;
  const map = new Map();
  const stack = [node];
  let clone = null;
  while (stack.length) {
    const last = stack.pop();
    if (!map.get(last)) {
      clone = new Node(last.val);
      map.set(last, clone);
    } else {
      clone = map.get(last)
    }
    last.neighbors.forEach(n => {
      if (!map.get(n)) {
        const temp = new Node(n.val);
        clone.neighbors.push(temp);
        map.set(n, temp);
        stack.unshift(n);
      } else {
        clone.neighbors.push(map.get(n));
      }
    })
  }
  return map.get(node);
}

广度优先遍历优化

const cloneGraph = (node) => {
  if (!node) return node;
  const map = new Map();
  const stack = [node];
  // 默认克隆第一个节点
  map.set(node, new Node(node.val));
  
  while (stack.length) {
    const next = stack.pop();
    next.neighbors.forEach(n => {
      if (!map.get(n)) {
        map.set(n, new Node(n.val));
        stack.unshift(n);
      } 
      //上一步已经在map中保存了节点，可以直接使用
      map.get(next).neighbors.push(map.get(n));
    })
  }
  return map.get(node);
}

打赏