怎么理解DFS和BFS
当遇到列举所有的情况之类的，要联想到DFS和BFS！ 就像看到直角三角形想到勾股定理，十之八九的要用到！
TL;DR
列举所有的情况常常使用两个思想：
- DFS（Deep First Search - 深度优先搜索）: 不撞南墙不回头，撞了南墙那就回头重新走。一般和二叉树的先序遍历紧密相关，用递归实现，本质是栈结构，后进先出
- BFS（Breath First Search - 广度优先搜索）: 雷达扫描式前进，看到新路就记着，走过的路就舍弃。一般和二叉树的层序遍历紧密相关，用队列实现，先进先出
DFS
DFS: 贯彻了“不撞南墙不回头”的原则，你在一个迷宫里，只要没有碰壁，就决不选择其它的道路，而是坚持向当前道路的深处挖掘，像这样将“深度”作为前进的第一要素的搜索方法，就是所谓的“深度优先搜索”。
深度优先搜索的核心思想，是试图穷举所有的完整路径。
网络异常，图片无法展示
|
- A-B-C，C 南墙，退到 B
- A-B-D，D 南墙，退到 B
- A-B-E-F，F 南墙，退到 E
- A-B-E-G-H，H 南墙，退到 G
- A-B-E-G-I，成功出口
深度优先搜索的过程可以转化为一系列的入栈、出栈操作，往往使用递归来模拟入栈、出栈的逻辑。
DFS 紧密相关：二叉树的先序遍历
网络异常，图片无法展示
|
{ val:'A', left:{ val:'B', left:{ val:'C' } } }
先序遍历：
// 所有遍历函数的入参都是树的根结点对象 function preorder(root) { // 递归边界，root 为空 if (!root) { return; } // 输出当前遍历的结点值 console.log("当前遍历的结点值是：", root.val); // 递归遍历左子树 preorder(root.left); // 递归遍历右子树 preorder(root.right); }
在这个递归函数中，递归式用来先后遍历左子树、右子树（分别探索不同的道路），递归边界在识别到结点为空时会直接返回（撞到了南墙）。
可以认为，递归式就是我们选择道路的过程，而递归边界就是死胡同。 二叉树的先序遍历正是深度优先搜索思想的递归实现。
为啥还说深度优先搜索的本质是栈呢？
两个角度来理解这个事情：
- 首先，递归的本质就是调用函数，而调用函数就会用到系统栈。
- 其次，DFS 作为一种思想，不是肯定会用到递归，有时候需要手动写栈结构
BFS
网络异常，图片无法展示
|
- A-B 走到 A，看到 B
- B-C-D-E 走到 B，舍弃 A，看到 CDE
- C-D-E 走到 C，舍弃 B，没看到啥
- D-E 走到 D，舍弃 D，没看到啥
- E-F-G 走到 E，舍弃 D，看到 FG
- F-G 走到 F，舍弃 E，没看到啥
- G-H-I 走到 G，舍弃 F，看到 HI
- H-I 走到 H，舍弃 G，没看到啥
- I-出口 走到 I，舍弃 H，看到出口
- 出口 走到出口，舍弃 I，问题解决
- 空 走出出口，问题解决
在分层遍历的过程中，两个规律：
- 每访问完毕一个坐标，其在后续遍历中就不需要了，可以被丢弃掉。
- 站在某个确定坐标的位置上，可直接抵达的坐标，是需要被记录下来的，因为后续的遍历还要用到它们。
丢弃已访问的坐标、记录新观察到的坐标，这个顺序毫无疑问符合了“先进先出”的原则，因此整个 BFS 算法的实现过程，和队列有着密不可分的关系。
伪代码表示上面的逻辑：
function BFS(入口坐标) { // 初始化队列queue const queue = [] // 入口坐标首先入队 queue.push(入口坐标) // 队列不为空，说明没有遍历完全 while(queue.length) { // 取出队头元素 const top = queue[0] // 此处是一些和 top 相关的逻辑，比如记录它对应的信息、检查它的属性等等 访问 top // 注意这里也可以不用 for 循环，视题意而定 for(检查 top 元素出发能够遍历到的所有元素) { queue.push(top能够直接抵达的元素) } // 访问完毕。将队头元素出队 queue.shift() } }
BFS 紧密相关：二叉树的层序遍历
网络异常，图片无法展示
|
二叉树的层序遍历，其实就是 BFS 的思想：
const root = { val: "A", left: { val: "B", left: { val: "D", }, right: { val: "E", }, }, right: { val: "C", right: { val: "F", }, }, }; function BFS(root) { let queue = []; // 根结点首先入队 queue.push(root); // 队列不为空，说明没有遍历完全 while (queue.length) { // 这里队列前面不断被更新 const top = queue[0]; // 输出值 console.log(top.val); // 将可到达的点 入队 top.left && queue.push(top.left); top.right && queue.push(top.right); // 访问完毕，队头元素出队 queue.shift(); } } BFS(root);
