DFS （深度优先遍历）和 BFS (广度优先遍历）

  <div class="parent">
    <div class="child-1">
      <div class="child-1-1">
        <div class="child-1-1-1">
          <div>342</div>
        </div>
      </div>
      <div class="child-1-2">
        <div class="child-1-2-1">b</div>
      </div>
      <div class="child-1-3">c</div>
    </div>
    <div class="child-2">
      <div class="child-2-1">d</div>
      <div class="child-2-2">e</div>
    </div>
    <div class="child-3">
      <div class="child-3-1">f</div>
    </div>
  </div>

这里用一棵dom树来做说明

深度优先遍历

假设初始状态的时候图中的所有顶点均未被访问，则从某个个顶点v出发，首先访问该顶点，然后从它的各个未被访问的邻接点出发进行向下遍历

• 递归操作

const deepTraversal1 = (node, nodeList = []) => {
  if (node !== null) {
    nodeList.push(node)
    let children = node.children
    for (let i = 0; i < children.length; i++) {
      deepTraversal1(children[i], nodeList)
    }
  }
  return nodeList
}

• 非递归

// 深度遍历 方法一： 非递归方式实现
const deepTraversal2 = (node) => {
  let stack = []
  let nodes = []
  if (node) {
    // 推入当前处理的node
    stack.push(node)
    while (stack.length) {
      let item = stack.pop()
      let children = item.children
      nodes.push(item)
      // node = [] stack = [parent]
      // node = [parent] stack = [child3,child2,child1]
      // node = [parent, child1] stack = [child3,child2,child1-2,child1-1]
      // node = [parent, child1-1] stack = [child3,child2,child1-2]
      for (let i = children.length - 1; i >= 0; i--) { // mei
        stack.push(children[i])
      }
    }
  }
  return nodes
}

解释下最后一个：（可能会后面的广度优先冲突）
这个是深度优先的，你看看它最后的循环，是从末尾开始，也就是说，再下一次循环进来的时候，每次出栈都是从后面最后一个开始[其实已经到了子节点的范畴了】，[(当前节点的子节点是被放在栈的后面）

广度优先遍历

从图中的某个顶点v出发，在访问v之后依次访问v的各个未曾相邻的邻接节点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。

const widthTraversal = (node) => {
  let nodes = []
  let queue = []
  console.log('start')
  if (node) {
    queue.push(node)
    while (queue.length) {
      let item = queue.shift()
      let children = item.children
      console.log(item)
      nodes.push(item)
        // 队列，先进先出
        // nodes = [] stack = [parent]
        // nodes = [parent] stack = [child1,child2,child3]
        // nodes = [parent, child1] stack = [child2,child3,child1-1,child1-2]
        // nodes = [parent,child1,child2]
      for (let i = 0; i < children.length; i++) {
        queue.push(children[i])
      }
    }
  }
  return nodes
}

const parent = document.querySelector('.parent')
// const result = deepTraversal1(parent) // 深度遍历 递归
// const result = deepTraversal2(parent) // 深度遍历 非递归
console.log('123')
const result = widthTraversal(parent) // 广度遍历
console.log(result)

参考：https://github.com/Advanced-Frontend/Daily-Interview-Question/issues/9