DFS

DFS 的英文全称 Depth First Search，即深度优先搜索

深度优先搜索的核心思想是试图穷举所有的完整路径。

深度优先搜索的本质是栈结构。

我们来看下二叉树的先序遍历：

二叉树的先序遍历就是深度优先搜索思想的递归实现。

function preorder(root) {
  if (!root) return root;
  console.log(root.val);
  preorder(root.left);
  preorder(root.right);
}

BFS

BFS 的英文全称是 Breadth First Search ，即广度优先原则。广度优先以 “广度” 为第一要务，一层层扫描，如下图：

BFS 的实现和队列有着很密切的关系。

还以二叉树为例，我们看下二叉树的层序遍历，如下图：

代码实现：

function BFS(root) {
  const queue = [];
  queue.push(root);
  while (queue.length) {
    const top = queue[0];
    console.log(top.val);
    if (top.left) {
      queue.push(top.left);
    }
    if (top.right) {
      queue.push(top.right);
    }
    queue.unshift();
  }
}

BFS(root);

/* 
A
B
C
D
E
F
*/