介绍下深度优先遍历和广度优先遍历，如何实现

[ZhengXingchi]

深度优先遍历方式

 function dfs(node, nodeList = []) {
      nodeList.push(node)
      let children = node.children
      if (children.length > 0) {
        children.forEach(i => {
          dfs(i, nodeList)
        })
      }
      return nodeList
    }

深度优先stack方式

   function dfs(node) {
      let stack = []
      let nodeList = []
      stack.push(node)
      nodeList.push(node)
      do {
        let current = stack.pop()
        nodeList.push(current)
        let children = current.children
        if (children.length > 0) {
          for (let i = children.length - 1; i > 0; i--) {
            stack.push(children[i])
          }
        }
      } while (stack.length > 0)
    }

[ZhengXingchi]

广度优先遍历quene方式

  function bfs(node) {
      let quene = []
      let nodeList = []
      nodeList.push(node)
      quene.push(node)
      do {
        let current = quene.shift()
        nodeList.push(current)
        let children = current.children
        if (chiledren.length > 0) {
          children.forEach(i => [
            quene.push(i)
          ])
        }
      } while (quene.length > 0)
    }

[ZhengXingchi]

广度遍历递归实现

    function bfs(node, nodeList = [], count = 0) {
      if (nodeList.length === 0) {
        nodeList.push(node)
      } else {
        let children = node.children
        if (children.length > 0) {
          nodeList = nodeList.concat(children)
        }
      }
      bfs(nodeList[count], nodeList, count++)
      return nodeList
    }

[ZhengXingchi]

深度遍历实现深拷贝

 function dfs(obj) {
      let target
      if (typeof obj !== 'object') {
        return obj
      }
      if (type(obj) === '[object Array]') {
        let output = []
        obj.forEach(i => {
          output.push(dfs(i))
        })
        return output
      }
      if (type(obj) === '[object Object]') {
        let output = {}
        Object.keys(obj).forEach(key => {
          output[key] = dfs(obj[key])
        })
        return output
      }
    }
    function type(v) {
      return Object.prototype.toString.call(v)
    }

[ZhengXingchi]

广度遍历实现深拷贝

  function bfs(obj) {
      let quene = []
      let target = getEmpty(obj)
      if (target !== obj) {
        quene.push([obj, target])
      }
      while (quene.length) {

        let [o, tar] = quene.shift()
        for (let i in o) {
          tar[i] = getEmpty(o[i])
          if (tar[i] !== o[i]) {
            quene.push([o[i], tar[i]])
          }
        }
      }
      return target
    }
    function getEmpty(o) {
      if (Object.prototype.toString.call(o) === '[object Object]') {
        return {}
      }
      else if (Object.prototype.toString.call(o) === '[object Array]') {
        return []
      }
      else {
        return o
      }
    }