深度优先搜索（DFS）和广度优先搜索（BFS）是两种基本的算法思想，其本质分别是栈和队列，在二叉树的遍历中有着重要的应用

DFS

二叉树前序遍历（中序遍历，后续遍历）的递归实现就是DFS，按照根-左-右的顺序进行遍历，

function preorder(root) {
  const res = []
  DFS(root)
  function DFS(root){ // 深度优先搜索
    // 递归边界
    if(!root) return 
    res.push(root.val)
    // 递归遍历左子树
    DFS(root.left)
    // 递归遍历右子树
    DFS(root.right)
  }
  return res
}
console.log(preorder(root))
// [ 'A', 'B', 'D', 'E', 'C', 'F' ]

上面代码表示前序遍历是通过递归实现的，而递归的本质是函数调用栈，最外层的函数先调用（进栈），但最后执行完（出栈），所以说DFS的本质是栈

BFS

二叉树层序遍历

二叉树的层序遍历就是BFS，即一层一层的遍历，每层从左到右的访问

function BFS(root){
  const queue = []
  queue.push(root) // 队列进
  while(queue.length){
    const top = queue.shift() // 访问完就要出列的元素
    console.log(top.val)
    if(top.left){
      queue.push(top.left)
    }
    if(top.right){
      queue.push(top.right)
    }
  }
}
BFS(root) // ABCDEF

上面可以看出，BFS的本质是一个队列结构
我们在访问一层的时候，把下层的内容放进了队列里面，然后本层访问过的内容出列，直到队列为空结束

层序遍历衍生问题（LeetCode 102）

给你一个二叉树，返回由层序遍历得到数组，其中每层的元素组成一个数组

示例：上面的二叉树返回： [ [ ‘A’ ], [ ‘B’, ‘C’ ], [ ‘D’, ‘E’, ‘F’ ] ]
思路分析：
本质还是BFS + 队列，但是根据队列的长度对结果进行了分组

var levelOrder = function(root) {
  const res = []
  if(!root){
    return res
  } 
  const queue = [] // 辅助队列
  queue.push(root)
  while(queue.length){
    const level = []
    const len = queue.length // 每层的元素个数
    for(let i=0; i<len; i++){
      const top = queue.shift()
      level.push(top.val)
      top.left && queue.push(top.left)
      top.right && queue.push(top.right)
    }
    res.push(level)
  }
  return res
};