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

深度优先遍历（DFS）

主要思路是从未访问的顶点开始，沿着一条路一直走到底，然后从这条路尽头的节点回退到上一个节点，再从另一条路开始走到底…，不断递归重复此过程，直到所有的顶点都遍历完成，它的特点是不撞南墙不回头，先走完一条路，再换一条路继续走。
先序遍历、中序遍历、后序遍历都是深度优先遍历。

// 下面是先序遍历一个树
function first (node){
  if(!node)return
  console.log(node.val)
  fn(node.left)
  fn(node.right)
}

// 下面是中序遍历一个树
function second (node){
  if(!node) return
  second(node.left)
  console.log(node.val)
  second(node.right)
}

// 下面是后序遍历一个树
function third (node){
  if(!node) return
  third(node.left)
  third(node.right)
  console.log(node.val)
}

function dfs(root: TreeNode | null): number[][] {
  first(root)
  second(root)
  third(root)
};

用栈实现一个先序遍历

const preorderTraversal = function(root) {
    const stack = [], res = []
    root && stack.push(root)
    // 使用一个栈stack，每次首先输出栈顶元素，也就是当前二叉树根节点，之后依次输出二叉树的左孩子和右孩子
    while(stack.length > 0) {
        let cur = stack.pop()
        console.log(cur.val)
        // 先入栈的元素后输出，所以先入栈当前节点右孩子，再入栈左孩子
        cur.right && stack.push(cur.right)
        cur.left && stack.push(cur.left)
    }
    return res
};

广度优先遍历（BFS）

用队列实现一个层序遍历

function BFS_By_Queue(root) {
  if (root === null) return
  let queue = [root]
  while(queue.length) {
      let { left, right, val } = queue.shift() // 队列，先进先出。先遍历顶层节点
      console.log(val)
      left && queue.push(left)
      right && queue.push(right)
  }
}