❓请分别用深度优先思想和广度优先思想实现一个拷贝函数？

这道题目刚刚好跟我们上面的一道关联性很强，经过上面的深度广度优先遍历我们知道了它们的遍历思想。那么结合这道题目。

假设我们有一个目标对象：

const testTarget = {
  name: 'jeff',
  tree: {
    value: 'root',
    children: [
      {
        value: 'A',
        children: [
          { value: 'A-a', children: [{ value: 'A-a-1' }, { value: 'A-a-2' }] },
          { value: 'A-b', children: [{ value: 'A-b-1' }, { value: 'A-b-2' }] },
        ],
      },
      {
        value: 'B',
        children: [
          { value: 'B-a', children: [{ value: 'B-a-1' }, { value: 'B-a-2' }] },
          { value: 'B-b', children: [{ value: 'B-b-1' }, { value: 'B-b-2' }] },
        ],
      },
      {
        value: 'C',
        children: [
          { value: 'C-a', children: [{ value: 'C-a-1' }, { value: 'C-a-2' }] },
          { value: 'C-b', children: [{ value: 'C-b-1' }, { value: 'C-b-2' }] },
        ],
      },
    ],
  },
  deepQuote: null,
}

我们的一些辅助函数很有用的哦。

// 辅助函数
const typeMap = {
  array: 'Array',
  object: 'Object',
  function: 'Function',
  string: 'String',
  null: 'Null',
  undefined: 'Undefined',
  boolean: 'Boolean',
  number: 'Number',
}
const isTypeOf = (obj, type) =>
  Object.prototype.toString.call(obj).slice(8, -1) === typeMap[type]

function getEmpty(o) {
  // console.log(o); // 可以看到每次循环的值
  if (isTypeof(o, 'object')) return {}
  if (isTypeof(o, 'array')) return []
  if (isTypeof(o, 'function')) {
    return new Function(
      `"use strict;" return (function() {return ${o.toString()}})`
    )
  }
  if (isTypeof(o, 'regexp')) {
    const reFlagReg = /\w*$/
    const reg = new RegExp(o.source, reFlagReg.exec(o))
    reg.lastIndex = o.lastIndex
    return reg
  }
  return o
}

深度优先思想

// 如果有循环引用的关系，就是环形引用
// testTarget.deepQuote = testTarget;

// 深度优先思想
// 第二个参数解决循环引用
function dfsDeepClone(target, verifyArr = []) {
  let result = null

  if (isTypeOf(target, 'object')) {
    result = {}
    for (const key in target) {
      if (target.hasOwnProperty(key)) {
        const element = target[key]
        // console.log(element);
        // 验证是否遍历过这个对象
        if (verifyArr.includes(element)) {
          result[key] = element
        } else {
          verifyArr.push(element)
          // 这里记得把 verifyArr 数组调用时候带入
          result[key] = dfsDeepClone(element, verifyArr)
        }
      }
    }
  } else if (isTypeOf(target, 'array')) {
    result = []
    for (let index = 0; index < target.length; index++) {
      const element = target[index]
      // console.log(element);
      // 验证是否遍历过这个对象
      if (verifyArr.includes(element)) {
        result.push(element)
      } else {
        verifyArr.push(element)
        // 这里记得把 verifyArr 数组调用时候带入
        result.push(dfsDeepClone(element, verifyArr))
      }
    }
  } else if (isTypeOf(target, 'function')) {
    result = Function(
      `"use strict"; return (function() {return ${target.toString()}})`
    )
  } else {
    result = target
  }

  return result
}

function dfsDeepClone2(target) {
  let result = getEmpty(target) // 返回值
  let stack = [] // 循环队列
  let recordMap = new Map()

  function checkCurrent(t, r) {
    if (t !== r) {
      // 说明是引用类型
      stack.push([t, r])
      recordMap.set(t, r)
    }
  }
  checkCurrent(target, result)

  while (stack.length) {
    let [tar, res] = stack.pop()
    for (const key in tar) {
      let element = tar[key]
      // 判断是否是环数据
      if (recordMap.has(element)) {
        res[key] = recordMap.get(element)
        continue
      }
      // 赋值 getEmpty 里面会返回不是引用类型的值
      res[key] = getEmpty(element)

      // 判断结果值 推入队列
      checkCurrent(element, res[key])
    }
  }
  return result
}

const dfsDeepCloneResult = dfsDeepClone(testTarget)
// 如果把上面的循环引用打开的话，这里会报错
// Converting circular structure to JSON
console.log(JSON.stringify(dfsDeepCloneResult))
// 这里的结果我就不展示了。
// 有兴趣可以去跑一下 https://github.com/lqk9511/blog/blob/master/docs/interview/test/6.js

广度优先思想

// 广度优先思想
function bfsDeepClone(target) {
  let result = getEmpty(target) // 返回值
  let queue = [] // 循环队列
  let recordMap = new Map() // 记录循环引用变量 解决环数据问题
  function checkCurrent(t, r) {
    if (t !== r) {
      // 说明是引用类型
      queue.push([t, r])
      recordMap.set(t, r)
    }
  }
  checkCurrent(target, result)

  while (queue.length) {
    let [tar, res] = queue.shift()
    for (const key in tar) {
      let element = tar[key]
      // 判断环引用
      if (recordMap.has(element)) {
        res[key] = recordMap.get(element)
        continue
      }
      // 判断目标值
      res[key] = getEmpty(element)
      // 如果得到结果值跟目标值不一样 添加队列 循环
      checkCurrent(element, res[key])
    }
  }
  return result
}

// const bfsDeepCloneResult = bfsDeepClone(testTarget);
// console.log(JSON.stringify(bfsDeepCloneResult));

完整代码

也有参考别的大佬的思路啦～在这里

其实解算法题，我觉得重要的还是思考的思路，以及你对其的切入点。还有你的见识啦，读万卷书，搬万顿砖。

思路都在代码里面了，看看注释哦，不行就 debugger 咯，一起进步嘛。

就像我首页的那张图一样 “YOU CAN DO IT!” （好吧，我承认是“贫穷使我们相遇”。）