【前端100问】Q6：请分别用深度优先思想和广度优先思想实现一个

写在前面

此系列来源于开源项目：前端 100 问：能搞懂 80%的请把简历给我
为了备战 2021 春招
每天一题，督促自己
从多方面多角度总结答案，丰富知识
请分别用深度优先思想和广度优先思想实现一个拷贝函数？

正文回答

只深拷贝了 Object, Array，其他的非基本类型都是浅拷贝（如果处理 Set 什么的就太复杂了，题目用意应该是考察遍历树和重复引用吧）

DFS 用常规的递归问题不大，需要注意下重复引用的问题，不用递归的话就用栈

BFS 就用队列，整体代码倒是差不多

// 如果是对象/数组，返回一个空的对象/数组，
// 都不是的话直接返回原对象
// 判断返回的对象和原有对象是否相同就可以知道是否需要继续深拷贝
// 处理其他的数据类型的话就在这里加判断
function getEmpty(o) {
  if (Object.prototype.toString.call(o) === "[object Object]") {
    return {};
  }
  if (Object.prototype.toString.call(o) === "[object Array]") {
    return [];
  }
  return o;
}

function deepCopyBFS(origin) {
  let queue = [];
  let map = new Map(); // 记录出现过的对象，用于处理环

  let target = getEmpty(origin);
  if (target !== origin) {
    queue.push([origin, target]);
    map.set(origin, target);
  }

  while (queue.length) {
    let [ori, tar] = queue.shift();
    for (let key in ori) {
      // 处理环状
      if (map.get(ori[key])) {
        tar[key] = map.get(ori[key]);
        continue;
      }

      tar[key] = getEmpty(ori[key]);
      if (tar[key] !== ori[key]) {
        queue.push([ori[key], tar[key]]);
        map.set(ori[key], tar[key]);
      }
    }
  }

  return target;
}

function deepCopyDFS(origin) {
  let stack = [];
  let map = new Map(); // 记录出现过的对象，用于处理环

  let target = getEmpty(origin);
  if (target !== origin) {
    stack.push([origin, target]);
    map.set(origin, target);
  }

  while (stack.length) {
    let [ori, tar] = stack.pop();
    for (let key in ori) {
      // 处理环状
      if (map.get(ori[key])) {
        tar[key] = map.get(ori[key]);
        continue;
      }

      tar[key] = getEmpty(ori[key]);
      if (tar[key] !== ori[key]) {
        stack.push([ori[key], tar[key]]);
        map.set(ori[key], tar[key]);
      }
    }
  }

  return target;
}

// test
[deepCopyBFS, deepCopyDFS].forEach((deepCopy) => {
  console.log(deepCopy({ a: 1 }));
  console.log(deepCopy([1, 2, { a: [3, 4] }]));
  console.log(
    deepCopy(function () {
      return 1;
    })
  );
  console.log(
    deepCopy({
      x: function () {
        return "x";
      },
      val: 3,
      arr: [1, { test: 1 }],
    })
  );

  let circle = {};
  circle.child = circle;
  console.log(deepCopy(circle));
});