力扣入门级广度优先搜索/遍历刷题小结

刷这些题时死掉的脑细胞是我当年在《线性代数》和《概率论与数理统计》课上没学明白时苟活下来的（
这几题基本是抄作业了，但我发现官方题解写的也很绕，都不知道是我天然看到这类题就头晕眼花春困秋乏还是怎么，总之使劲把自己掐清醒后把题目和官方题解以我自己能看懂的文字记录下来。

首先记一下两个专有名词的专有缩写：
广度优先搜索/遍历：BFS
深度优先搜索/遍历：DFS

相关计划：20天算法刷题计划
相关题目：

733.图像渲染
695.岛屿的最大面积
617.合并二叉树
116.填充每个节点的下一个右侧节点指针
542.01矩阵
994.腐烂的橘子

733.图像渲染

题干

有一幅以 m x n 的二维整数数组表示的图画 image ，其中 image[i][j] 表示该图画的像素值大小。
你也被给予三个整数 sr , sc 和 newColor 。你应该从像素 image[sr][sc] 开始对图像进行 上色填充 。
为了完成 上色工作 ，从初始像素开始，记录初始坐标的 上下左右四个方向上 像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应 四个方向上 像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为 newColor 。
最后返回 经过上色渲染后的图像 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/flood-fill

思路

这题官方给出的方法有两种，一是广度优先搜索，二是深度优先搜索，这里先记录前者。
广度优先搜索的思路是：从给定起点开始，每搜索到一个方格时，若其与初始方格颜色一致，则将其入队并更新颜色，即改值，以防重复入队。
是故，需要使用队列完成。
这条队即是需要遍历其上下左右四顶点的方格坐标汇总，粗暴理解，就是选择/魔术棒/钢笔工具画出来的边界，改值的部分即为油漆桶上色（这里感谢万能的评论区） 。

复杂度

时间复杂度：O(n×m)，其中 n 和 m 分别是二维数组的行数和列数。最坏情况下需要遍历所有空格。
空间复杂度：O(n×m)，其中 n 和 m 分别是二维数组的行数和列数。主要为队列的开销。

代码

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
        # 保留原始方格颜色
        currentColor = image[sr][sc]
        if currentColor == newColor:
            return image
        # 行数（高）和列数（宽）
        row_size = len(image)
        col_size = len(image[0]) 
        # 先来个队列，放个初始给定格子
        queue = collections.deque([(sr,sc)])
        # 上色
        image[sr][sc] = newColor
        # 遍历
        while(queue):
            # 出队 
            r,c = queue.popleft()
            # 在上下左右四格里遍历
            for mr,mc in [(r-1,c),(r+1,c),(r,c-1),(r,c+1)]:
                # 判断要求：行列值是否在image范围内？该位置值是否等于初始值？
                if mr>=0 and mr<row_size and mc>=0 and mc<col_size and image[mr][mc]==currentColor:
                    # 上色
                    image[mr][mc]=newColor
                    # 入队
                    queue.append([mr,mc])
        return image

695.岛屿的最大面积（最大岛屿的面积）

这题我还是觉得要改成括号里的才好……不然第一反应是计算涨落潮导致的岛屿面积变化……结果题干就是让你找出下列地图中面积最大的岛屿并返回其面积。

题干

给你一个大小为 m x n 的二进制矩阵 grid 。 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1
必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。 岛屿的面积是岛上值为 1
的单元格的数目。 计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。 来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/max-area-of-island
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这道题同样有广度优先搜索和深度优先搜索两种思路，其中后者在官方解法里甚至有两种（第二种使用了栈的思路）。这里仍旧只记录广度优先搜索的解法（使用队列）。
官方思路如下：
1、从给定位置出发，以 4 个方向探索与之相连的每一个单元格（以及与这些格子相连的单元格），则探索过的单元格总数将是该岛屿的面积。
2、探索时从队列取出第一个元素，将下一步需要探索的格子放入队列末尾
3、为确保每个格子只访问 1 次，每经过时将其赋值为 0 。

复杂度

时间复杂度：O(R × C) 其中 R 是给定网格中的行数，C 是列数。访问每个网格最多一次。
空间复杂度：O(R × C) ，队列中最多会存放所有的土地，土地的数量最多为 R×C 块，因此使用的空间为 O(R×C)。

代码

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        ans = 0 # 要返回的最大岛屿面积
        # 逐行逐列遍历
        for i,l in enumerate(grid):
            for j,n in enumerate(l):
                cur = 0
                q = collections.deque([(i,j)])
                while q:
                    cur_i,cur_j = q.popleft()
                    #如果是0，跳过while的后续步骤
                    if cur_i<0 or cur_j<0 or cur_i==len(grid) or cur_j==len(grid[0]) or grid[cur_i][cur_j]!=1:
                        continue
                    #否则递增1
                    cur += 1
                    #并置0
                    grid[cur_i][cur_j]=0
                    #取上下左右各点入队
                    for di,dj in [[0,1],[0,-1],[1,0],[-1,0]]:
                        next_i,next_j = cur_i+di,cur_j + dj
                        q.append((next_i,next_j))
                #↑while即可保证队列里是“岛屿”，从而计算岛屿面积

                #比较ans和岛屿面积计算后的值，取其最大者赋予ans
                ans = max(ans,cur)
        return ans

由于先前算法基础知识不熟，在考虑时过于纠结 “ 不可能整个二维数组遍历一遍吧这样想肯定不对吧 ” 于是看到两个 for 套用时我傻眼了（。
怎么说，结论是要想飞先要会跑吧。
善用评论区，一般官方解法拗口得看不懂的经常可以在评论区看到大白话讲解，以及更多解法。受益匪浅。

617.合并二叉树

题干

给你两棵二叉树： root1 和 root2 。
想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为
null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-two-binary-trees
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

此题同样有两种官方解法，一是深度优先搜索，二是广度优先搜索。不知道为什么我抄作业抄了第一种……不过也有可能是对树来讲，深度优先的解法更符合一般想象。
这里同样只记录广度优先的逻辑。深度优先的等后面再统一在另一个笔记里。
首先，判断两个二叉树是否为空

• 都是空，那返回空
• 只一个空，则返回另一个
• 都不为空，进入下一步

第二步如下：

1. 计算合并后的根节点的值
2. 从合并后的根节点开始，对两棵树开始遍历，将遍历到的节点合并
   这里需要用到三个队列，分别存储原始两棵树及合并后的树的下一个需要遍历的节点。初始时将每个二叉树的根节点分别放入队列中。
   每次从队列中取出一个节点，判断其所在树的左右子节点是否为空：

• 若一个为空，则取另一个作为合并后的子节点
• 若两个都不空，则相加后作为合并后的子节点，并将三个点加入各自队列
• 若两个都空，就不管了，直接都读下一个节点

后面的就是重复以上循环了
总感觉写出来也没有多明确。。
官方广度优先搜索的代码如下，注释是我自己加的

复杂度

时间：O(N)
空间：O(N)

代码

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
        if not t1:
            return t2
        if not t2:
            return t1
        
        merged = TreeNode(t1.val + t2.val)
        # 初始队列
        queue = collections.deque([merged]) # 合并后的节点
        queue1 = collections.deque([t1])
        queue2 = collections.deque([t2])

        while queue1 and queue2:
            node = queue.popleft()
            node1 = queue1.popleft()
            node2 = queue2.popleft()
            left1, right1 = node1.left, node1.right
            left2, right2 = node2.left, node2.right
            # 如果两个子节点有任一非空
            if left1 or left2:
                # 若同时非空
                if left1 and left2:
                    # 相加两者值，并各自入队
                    left = TreeNode(left1.val + left2.val)
                    node.left = left
                    queue.append(left)
                    queue1.append(left1)
                    queue2.append(left2)
                # 若只有左一
                elif left1:
                    node.left = left1
                # 若只有左二
                elif left2:
                    node.left = left2
            # 同上的判断
            if right1 or right2:
                if right1 and right2:
                    right = TreeNode(right1.val + right2.val)
                    node.right = right
                    queue.append(right)
                    queue1.append(right1)
                    queue2.append(right2)
                elif right1:
                    node.right = right1
                elif right2:
                    node.right = right2
        
        return merged

这道题用广度优先搜索的不多，评论和题解区大多是深度优先搜索的优化，这里就放另一篇笔记再说了。

116.填充每个节点的下一个右侧节点指针

这是一道乍一眼没看懂在说什么的题……

题干

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node { int val; Node *left; Node *right; Node *next; }
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这道题的第一种解法是层次遍历，即把二叉树每一层的节点都拿出来遍历并连接。这种遍历基于广度优先搜索，同样需要队列来实现。在遍历过程中修改每个节点的 next 指针，同时拓展下一层的新队列。但题干在末尾提出的进阶版里要求使用常量的辅助空间，这种解法的时间/空间复杂度均为 O(N) ，就不符合要求了（常量空间要求 O(1)）。
于是就有了第二种递归解法，以下思路及截图取自题解区大佬王尼玛。
第二种解法首先明确了结果串联树中节点的连接方式：

1. 两个节点共有一个父节点，则 n(left).next -> n.parent.right
2. 两个节点的父节点不同，但父节点彼此之间已经相连，于是 n(right).next -> n.parent.next.left
   
   此时需要保证的只有root.next不为空

复杂度

时间：O(N)
空间：O(1)

代码

此处贴一些官方和精选作者王尼玛的代码，我自己这道题当时没做出来，所以学习一下。

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        
        if not root:
            return root
        
        # 从根节点开始
        leftmost = root
        
        while leftmost.left:
            
            # 遍历这一层节点组织成的链表，为下一层的节点更新 next 指针
            head = leftmost
            while head:
                
                # CONNECTION 1
                head.left.next = head.right
                
                # CONNECTION 2
                if head.next:
                    head.right.next = head.next.left
                
                # 指针向后移动
                head = head.next
            
            # 去下一层的最左的节点
            leftmost = leftmost.left
        
        return root 

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/solution/tian-chong-mei-ge-jie-dian-de-xia-yi-ge-you-ce-2-4/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。


class Solution(object):
	def connect(self, root):
		""" :type root: Node :rtype: Node """
		if not root:
			return root
		pre = root
		# 循环条件是当前节点的left不为空，当只有根节点
		# 或所有叶子节点都出串联完后循环就退出了
		while pre.left:
			tmp = pre
			while tmp:
				# 将tmp的左右节点都串联起来
				# 注:外层循环已经判断了当前节点的left不为空
				tmp.left.next = tmp.right
				# 下一个不为空说明上一层已经帮我们完成串联了
				if tmp.next:
					tmp.right.next = tmp.next.left
				# 继续右边遍历
				tmp = tmp.next
			# 从下一层的最左边开始遍历 
			pre = pre.left
		return root

作者：wang_ni_ma
链接：https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/solution/dong-hua-yan-shi-san-chong-shi-xian-116-tian-chong/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

在评论区看到别人的简单思路，在此记录学习一下：

对于一个{根，左，右}二叉树，需要填充的有三个next： 根->next 指向 NULL 左->next 指向 右 右->next 指向
根->next->左 递归停止条件为孩子结点为空，这里随便写了个root->left==NULL判断条件。

作者：WK-Luo
链接：https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/solution/di-gui-by-wk-luo-sjrx/
来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

542.01矩阵

题干

给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/01-matrix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这道题的进阶解法是动态规划，这里就先按下不提了。
首先官方给了两种方法：

1. 设 0 在矩阵中位置是 (i0, j0)，1 在矩阵中位置是 (i1, j1) ，则从 1 到 0 需要水平方向走 | i0 - i1 | ，竖直方向走 | j0 - j1 | ，距离即是 | i0 - i1 | + | j0 - j1 |。
2. 从 0 的位置开始广度优先搜索，可以找到从起点到其余所有点的最短距离。如果从矩阵的 x 搜索到了 y，且 y 还没有被搜索过，则 y 距离 0 的距离就等于 x 离 0 的距离加上 1 。

第一种方法在处理多个 0 的时候就需要用到动态规划，所以按下不提。使用第二种。
第二种在遇到多个 0 时，需将这些 0 的位置全部加入队列。从队列开始广度优先搜索。所有的 0 在这种方法中被视作整体，即 “超级 0 ” 。
官方解法的 “超级 0” 实在没看懂，贴一下题解区Sweetiee 大佬的思路讲解：

一、广度优先搜索 思路： 对于 「Tree 的 BFS」 （典型的「单源 BFS」） 大家都已经轻车熟路了：
首先把 root 节点入队，再一层一层无脑遍历就行了。 对于 「图 的 BFS」 （「多源 BFS」） 做法其实也是一样滴～，与 「Tree
的 BFS」的区别注意以下两条就 ok 辣～
Tree 只有 1 个 root，而图可以有多个源点，所以首先需要把多个源点都入队； Tree
是有向的因此不需要标识是否访问过，而对于无向图来说，必须得标志是否访问过哦！并且为了防止某个节点多次入队，需要在其入队之前就将其设置成已访问！【
看见很多人说自己的 BFS 超时了，坑就在这里哈哈哈
作者：sweetiee
链接：https://leetcode-cn.com/problems/01-matrix/solution/2chong-bfs-xiang-jie-dp-bi-xu-miao-dong-by-sweetie/
来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复杂度

时间复杂度：O(rc) ，其中 r 为矩阵行数，c 为矩阵列数，每个位置最多会入队 1 次，故为 O(rc)
空间复杂度：O(rc) ，其中 r 为矩阵行数，c 为矩阵列数，除答案数组外，最坏情况下矩阵里所有元素都是 0 ，全部加入队列，故需要 O(rc)

代码

代码是官方的，注释是自己的。并且在seen = set(zeroes_pos)这一步试踩坑，写在注释里了。

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        # m行数，n列数
        m,n = len(mat),len(mat[0])
        # 构造一个m行n列元素都是0的矩阵，即原矩阵的全0版
        dist = [[0]*n for _ in range(m)]
        # 两个遍历合并的写法，判断mat[i][j]是否是0，是则加入数组，以构造初始队列
        zeroes_pos = [(i,j) for i in range(m) for j in range(n) if mat[i][j]==0]
        # python3中需要用collections.deque(数组)来构建队列
        que = collections.deque(zeroes_pos)
        # 使用set（此处不能直接用数组，会提示超出时间限制，并且存在重复的元素，set能够避免重复数据）
        seen = set(zeroes_pos)

        # 广度优先搜索
        while que:
            i,j=que.popleft()
            # 取四个方向的位置组成数组
            for ni,nj in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
                # 判断坐标是否在边界内，且不存在于初始所有0所在的Set集合里
                if 0<=ni<m and 0<=nj<n and (ni,nj) not in seen:
                    # 是的话，赋该点值为前述从队列中取出的值+1，即在原值基础上加1而得的距离
                    dist[ni][nj] = dist[i][j]+1
                    # 将该点加入队列
                    que.append((ni,nj))
                    # 将该点加入set集合（此处不能直接用数组的append，会提示超出时间限制）
                    seen.add((ni,nj))
        return dist

994.腐烂的橘子

题干

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
值 0 代表空单元格； 值 1 代表新鲜橘子； 值 2 代表腐烂的橘子。 每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/rotting-oranges
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

有了前一道题，这一题倒是一眼可以看出要用多源广度优先搜索。
在万能的题解区，大佬一句话翻译题目：求腐烂橘子到所有新鲜橘子的最短路径
这道题搬运一下nettee大佬的题解，我觉得比官方的更简明

一开始，我们找出所有腐烂的橘子，将它们放入队列，作为第 0 层的结点。 然后进行 BFS
遍历，每个结点的相邻结点可能是上、下、左、右四个方向的结点，注意判断结点位于网格边界的特殊情况。
由于可能存在无法被污染的橘子，我们需要记录新鲜橘子的数量。在 BFS 中，每遍历到一个橘子（污染了一个橘子），就将新鲜橘子的数量减一。如果
BFS 结束后这个数量仍未减为零，说明存在无法被污染的橘子。
作者：nettee
链接：https://leetcode-cn.com/problems/rotting-oranges/solution/li-qing-si-lu-wei-shi-yao-yong-bfsyi-ji-ru-he-xie-/
来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复杂度

代码

这个是官方代码，使用了yield，但老实讲没太看明白用法……

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        # 广度优先搜索
        R,C=len(grid),len(grid[0])
        # 队列,第一遍遍历所有元素找初始腐烂橘
        queue = collections.deque()
        for r,row in enumerate(grid):
            for c,val in enumerate(row):
                if val==2:
                    queue.append((r,c,0))
        
        # 使用yield，使这个方法成为一个迭代器，可以next的那种
        def neighbors(r,c) -> (int,int):
            for nr,nc in ((r-1,c),(r,c-1),(r+1,c),(r,c+1)):
                if 0<=nr<R and 0<=nc<C:
                    yield nr,nc
        
        d = 0
        while queue:
            r,c,d = queue.popleft()
            for nr,nc in neighbors(r,c):
                if grid[nr][nc]==1:
                    grid[nr][nc]=2
                    queue.append((nr,nc,d+1))
        if any(1 in row for row in grid):
            return -1
        return d

后面看到题解区“腐烂的橘子”大佬写的python代码，感觉才是我这种菜鸡看得懂的，这里也贴一下记录。

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        row, col, time = len(grid), len(grid[0]), 0
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        queue = []
        # add the rotten orange to the queue
        for i in range(row):
            for j in range(col):
                if grid[i][j] == 2:
                    queue.append((i, j, time))
        # bfs
        while queue:
            i, j, time = queue.pop(0)
            for di, dj in directions:
                if 0 <= i + di < row and 0 <= j + dj < col and grid[i + di][j + dj] == 1:
                    grid[i + di][j + dj] = 2
                    queue.append((i + di, j + dj, time + 1))
        # if there are still fresh oranges, return -1
        for row in grid:
            if 1 in row: return -1

        return time

作者：z1m
链接：https://leetcode-cn.com/problems/rotting-oranges/solution/yan-du-you-xian-sou-suo-python3-c-by-z1m/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

下面的是nettee大佬的代码，搭配题解思路使用更佳。

def orangesRotting(self, grid: List[List[int]]) -> int:
    M = len(grid)
    N = len(grid[0])
    queue = []
    
    count = 0 # count 表示新鲜橘子的数量
    for r in range(M):
        for c in range(N):
            if grid[r][c] == 1:
                count += 1
            elif grid[r][c] == 2:
                queue.append((r, c))
                
    round = 0 # round 表示腐烂的轮数，或者分钟数
    while count > 0 and len(queue) > 0:
        round += 1 
        n = len(queue)
        for i in range(n):
            r, c = queue.pop(0)
            if r-1 >= 0 and grid[r-1][c] == 1:
                grid[r-1][c] = 2
                count -= 1
                queue.append((r-1, c))
            if r+1 < M and grid[r+1][c] == 1:
                grid[r+1][c] = 2
                count -= 1
                queue.append((r+1, c))
            if c-1 >= 0 and grid[r][c-1] == 1:
                grid[r][c-1] = 2
                count -= 1
                queue.append((r, c-1))
            if c+1 < N and grid[r][c+1] == 1:
                grid[r][c+1] = 2
                count -= 1
                queue.append((r, c+1))
    
    if count > 0:
        return -1
    else:
        return round

作者：nettee
链接：https://leetcode-cn.com/problems/rotting-oranges/solution/li-qing-si-lu-wei-shi-yao-yong-bfsyi-ji-ru-he-xie-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

总结

腐烂橘子那题还是得多看几遍……
BFS的代码模板普遍使用的队列。对于树，则根节点入队；对于多源图，则图中所有的源点入队。从队列开始遍历四个方向。这是到目前这几题给我的套路印象。
一些树类型的题目可以用深度优先搜索DFS，一些图类型的题目可以使用动态规划，这是下一步学习的重点了。