<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樹(shù)來(lái)做說(shuō)明

深度優(yōu)先遍歷

假設(shè)初始狀態(tài)的時(shí)候圖中的所有頂點(diǎn)均未被訪問(wèn)，則從某個(gè)個(gè)頂點(diǎn)v出發(fā)，首先訪問(wèn)該頂點(diǎn)，然后從它的各個(gè)未被訪問(wèn)的鄰接點(diǎn)出發(fā)進(jìn)行向下遍歷

• 遞歸操作

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
}

• 非遞歸

// 深度遍歷 方法一： 非遞歸方式實(shí)現(xiàn)
const deepTraversal2 = (node) => {
  let stack = []
  let nodes = []
  if (node) {
    // 推入當(dāng)前處理的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
}

解釋下最后一個(gè)：（可能會(huì)后面的廣度優(yōu)先沖突）
這個(gè)是深度優(yōu)先的，你看看它最后的循環(huán)，是從末尾開(kāi)始，也就是說(shuō)，再下一次循環(huán)進(jìn)來(lái)的時(shí)候，每次出棧都是從后面最后一個(gè)開(kāi)始[其實(shí)已經(jīng)到了子節(jié)點(diǎn)的范疇了】，[(當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)是被放在棧的后面）

廣度優(yōu)先遍歷

從圖中的某個(gè)頂點(diǎn)v出發(fā)，在訪問(wèn)v之后依次訪問(wèn)v的各個(gè)未曾相鄰的鄰接節(jié)點(diǎn)，并使得“先被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)先于后被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)被訪問(wèn)，直至圖中所有已被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)到。

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)
        // 隊(duì)列，先進(jìn)先出
        // 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