刷题笔记四：深度优先搜索‼️

个人这个章节很重要，经常被考到！还是跟以前的笔记一样，总结来源于作者高畅的LeetCode101, 题目都是来自leetcode, 题解用的语言是python！

核心：深度优先搜索和广度优先搜索是两种最常见的优先搜索方法，它们被广泛地运用在图和树等结构中进行搜索。本章先讲深度优先搜索。

深度优先搜索(depth-first seach，DFS)在搜索到一个新的节点时，立即对该新节点进行遍 历;因此遍历需要用先入后出的栈来实现，也可以通过与栈等价的递归来实现。对于树结构而言， 由于总是对新节点调用遍历，因此看起来是向着“深”的方向前进。 考虑如下一颗简单的树。我们从1号节点开始遍历，假如遍历顺序是从左子节点到右子节点， 那么按照优先向着“深”的方向前进的策略，假如我们使用递归实现，我们的遍历过程为 1(起 始节点)->2(遍历更深一层的左子节点)->4(遍历更深一层的左子节点)->2(无子节点，返回 父结点)->1(子节点均已完成遍历，返回父结点)->3(遍历更深一层的右子节点)->1(无子节 点，返回父结点)-> 结束程序(子节点均已完成遍历)。如果我们使用栈实现，我们的栈顶元素 的变化过程为 1->2->4->3。

深度优先搜索也可以用来检测环路:记录每个遍历过的节点的父节点，若一个节点被再次遍 历且父节点不同，则说明有环。我们也可以用之后会讲到的拓扑排序判断是否有环路，若最后存 在入度不为零的点，则说明有环。 有时我们可能会需要对已经搜索过的节点进行标记，以防止在遍历时重复搜索某个节点，这 种做法叫做状态记录或记忆化(memorization)。

涉及问题：
1.        695. Max Area of Island (Easy)： 给定一个二维的 0-1 矩阵，其中 0 表示海洋，1 表示陆地。单独的或相邻的陆地可以形成岛 屿，每个格子只与其上下左右四个格子相邻。求最大的岛屿面积。
题析：此题是十分标准的深度优先搜索题。一般来说，深度优先搜索类型的题可以分为主函数和辅函数，主函数用于遍历所有的搜索位置，判断是否可以开始搜索，如果 可以即在辅函数进行搜索。辅函数则负责深度优先搜索的递归调用。在辅函数里，一个一定要注意的点是辅函数内递归搜索时，边界条件的判定。边界判定一般 有两种写法，一种是先判定是否越界，只有在合法的情况下才进行下一步搜索(即判断放在调用 递归函数前);另一种是不管三七二十一先进行下一步搜索，待下一步搜索开始时再判断是否合 法(即判断放在辅函数第一行)。我们这里分别展示这两种写法。
当然，我们也可以使用栈 (stack)实现深度优先搜索，但因为栈与递归的调用原理相同，而递归相对便于实现，因此刷题时推荐使用递归式写法。不过在实际工程上，直接使用栈也是不错的的选择，一是因为便于理解，二是更不易出现递归栈满的情况。但是我一般喜欢用递归。
题解：请看图。

2.        547. Number of Provinces
题析：这道题的解题思路跟上面那道题相似却有差异。同样我们需要用到dfs，不同的是我们这次是对某个节点即矩阵里的一整排进行搜索，若是发现这个节点有connection， 即这排数组上有出现1，我们把它归到一个list 里可以命名为seen，表示这些数已经被考虑过了，直到我们搜索完这个节点的所有connection。这样就算是完成了一个省。然后我们继续走完整个matrix就可以了.这道题还能用广度优先搜索的方法来做，具体方法我会在广度优先的笔记里讲解。
题解：请看图。

3.        417. Pacific Atlantic Water Flow
题析： 这道题同样是能用深度和广度搜索的方法做，我们这里先讲深度搜索。我们首先要知道matrix边界的点都是能流向太平洋或者大西洋的，至于里面的点的水能不能流向大海，则要看里面的水位是否高于它的边界，我们这题就从边界开始搜索，若边界点a的临近点b有比它高的水位，则这个点b的水能往下流，我们继续追踪这个边界点b的旁边的点，若有点c的水位高于这个点，则可以用这个b点作为渠道，c点也能流向海里，以此内推，我们把能流向太平洋的点收集到一个set里，能流向大西洋的点收集到另外一个set里，直到遍历完整个矩阵。收集完了之后找出这两个set共同拥有的点，这些点既能流向太平洋也能流向大西洋，这就是我们要的答案。
题解：请看图。

笔记持续更新，小伙伴记得关注我，点赞➕收藏呀！