AI summary
type
status
date
slug
summary
category
tags
icon
password

从树结构的层序遍历开始

919. 完全二叉树插入器

完全二叉树 是每一层（除最后一层外）都是完全填充（即，节点数达到最大）的，并且所有的节点都尽可能地集中在左侧。
设计一种算法，将一个新节点插入到一个完整的二叉树中，并在插入后保持其完整。
实现 CBTInserter 类:
  • CBTInserter(TreeNode root) 使用头节点为 root 的给定树初始化该数据结构；
  • CBTInserter.insert(int v) 向树中插入一个值为 Node.val == val的新节点 TreeNode。使树保持完全二叉树的状态，并返回插入节点 TreeNode 的父节点的值；
  • CBTInserter.get_root() 将返回树的头节点。
这道题考察二叉树的层序遍历，你需要先做 BFS 遍历得到可以插入的节点，用队列维护。
代码如下：

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

给定一个二叉树。填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。
初始状态下，所有 next 指针都被设置为 NULL 。
这题和 116. 填充每个节点的下一个右侧节点指针 还不一样，输入的不是完全二叉树，所以不好直接用递归。
这题用 BFS 算法 进行层序遍历比较直观，在 for 循环，无非就是想办法遍历所有节点，然后把这个节点和相邻节点连起来罢了。
代码如下：

662. 二叉树最大宽度

给你一棵二叉树的根节点 root ，返回树的 最大宽度 。
树的 最大宽度 是所有层中最大的 宽度 。
每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。
题目数据保证答案将会在  32 位 带符号整数范围内。
这道题的解题关键是要给二叉树节点按行进行编号，然后你就可以通过每一行的最左侧节点和最右侧节点的编号推算出这一行的宽度，进而算出最大宽度：
notion image
而且，这样编号还可以通过父节点的编号计算得出左右子节点的编号：假设父节点的编号是 x，左子节点就是 2 * x，右子节点就是 2 * x + 1。
代码如下：

863. 二叉树中所有距离为 K 的结点

给定一个二叉树（具有根结点 root）， 一个目标结点 target ，和一个整数值 k ，返回到目标结点 target 距离为 k 的所有结点的值的数组。
答案可以以 任何顺序 返回。
notion image
与目标结点（值为 5）距离为 2 的结点，值分别为 7，4，以及 1。
这道题常规的解法就是把二叉树变成一幅「图」，然后在图中用 BFS 算法求距离 target 节点 k 步的所有节点。
代码如下：

310. 最小高度树

树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，任何一个没有简单环路的连通图都是一棵树。
给你一棵包含 n 个节点的树，标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表（每一个边都是一对标签），其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条无向边。
可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h 。在所有可能的树中，具有最小高度的树（即，min(h)）被称为 最小高度树 。
请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。
树的高度是指根节点和叶子节点之间最长向下路径上边的数量。
notion image
如图所示，当根是标签为 1 的节点时，树的高度是 1 ，这是唯一的最小高度树。
我认为这道题非常有意思。用标准的 BFS 算法框架 就可以解决，只是需要一些改变。我直接说解题思路，很容易理解：
  1. 首先，我们把题目输入的 edges 转换成邻接表。
  1. 然后，我们从叶子节点开始，一层一层地删除叶子节点（每删除一层叶子节点，就会产生新的叶子节点），直到剩下的节点数小于等于 2 个为止。之所以是 2 个而不是 1 个，是因为如果输入的这幅图两边完全对称，可能出现两个节点都可以作为根节点的情况。
  1. 最后剩下的这些节点，就是我们要找的最小高度树的根节点。
notion image
如何一层一层删除所有叶子节点呢？只要用 BFS 算法，借助一个队列就可以了，具体实现看代码吧。
肯定有读者会问，这种题怎么能想出来呢？这需要你熟悉 BFS 算法的执行过程。
我们常见的 BFS 是把树的根节点初始化到队列里，这样可以找到距离根节点最近的叶子节点。那么如果反过来，把所有叶子节点作为起点，一层一层向上进行层序遍历，那么就可以保证这棵树的宽度尽可能「均匀」，即不会出现左子树为空，右子树却很深的情况。这样一来，最终反向搜索到的根节点就是能够让树高最小的根节点。
代码如下：

较为简单的 BFS

841. 钥匙和房间

有 n 个房间，房间按从 0 到 n - 1 编号。最初，除 0 号房间外的其余所有房间都被锁住。你的目标是进入所有的房间。然而，你不能在没有获得钥匙的时候进入锁住的房间。
当你进入一个房间，你可能会在里面找到一套不同的钥匙，每把钥匙上都有对应的房间号，即表示钥匙可以打开的房间。你可以拿上所有钥匙去解锁其他房间。
给你一个数组 rooms 其中 rooms[i] 是你进入 i 号房间可以获得的钥匙集合。如果能进入 所有 房间返回 true，否则返回 false。
其实题目输入的就是一个 邻接表 形式表示的图。你心里那棵穷举树结构出来没有？只要抽象出了穷举树，我们用 DFS/BFS 算法 从节点 0 开始遍历这幅图就行了，看看是否所有的节点都被访问到了。
对于这道题的 BFS 解法我多说两句，因为本题只是问是否可以遍历完所有图，并没有问最短距离之类的问题，所以我选择了一种最简单的 BFS 写法，也就是没有 len(q) 的版本。
代码如下：

1306. 跳跃游戏 III

这里有一个非负整数数组 arr，你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时，你可以跳到 i + arr[i] 或者 i - arr[i]。
请你判断自己是否能够跳到对应元素值为 0 的 任一 下标处。
注意，不管是什么情况下，你都无法跳到数组之外。
这种题就是穷举呗，心里那棵树出来没有？每个位置可以向左跳或者向右跳，这就是两种选择，都穷举一遍，就形成一棵二叉树。注意需要用 visited 数组记录已经访问过的位置避免重复访问。
代码如下：

433. 最小基因变化

基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 'A'、'C'、'G' 和 'T' 之一。
假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。
  • 例如，"AACCGGTT" --> "AACCGGTA" 就是一次基因变化。
另有一个基因库 bank 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。（变化后的基因必须位于基因库 bank 中）
给你两个基因序列 start 和 end ，以及一个基因库 bank ，请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化，返回 -1 。
注意：起始基因序列 start 默认是有效的，但是它并不一定会出现在基因库中。
还是穷举树。
代码如下:
其中 sz 是 "size" 的缩写。

1926. 迷宫中离入口最近的出口

给你一个 m x n 的迷宫矩阵 maze （下标从 0 开始），矩阵中有空格子（用 '.' 表示）和墙（用 '+' 表示）。同时给你迷宫的入口 entrance ，用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。
每一步操作，你可以往 上，下，左 或者 右 移动一个格子。你不能进入墙所在的格子，你也不能离开迷宫。你的目标是找到离 entrance 最近 的出口。出口 的含义是 maze 边界 上的 空格子。entrance 格子 不算 出口。
请你返回从 entrance 到最近出口的最短路径的 步数 ，如果不存在这样的路径，请你返回 -1 。
这道题非常简单，就是标准的 BFS 算法，只要套用框架就可以了，直接看代码吧。另外我建议做一下 286. 墙与门，比这道题有意思一些。
代码如下：

1091. 二进制矩阵中的最短路径

给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径，返回 -1 。
二进制矩阵中的 畅通路径 是一条从 左上角 单元格（即，(0, 0)）到 右下角 单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下述要求：
  • 路径途经的所有单元格的值都是 0 。
  • 路径中所有相邻的单元格应当在 8 个方向之一 上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。
畅通路径的长度 是该路径途经的单元格总数。
这道题的思路应该很明显，BFS 算法 肯定可以解决。
一般我们二维矩阵相关的题目只允许上下左右移动，这里还允许斜着移动，只要稍微改一改方向数组 dirs 即可。
代码如下：

BFS 在实际场景中的有趣应用

994. 腐烂的橘子

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
  • 值 0 代表空单元格；
  • 值 1 代表新鲜橘子；
  • 值 2 代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
这就是标准的 BFS 算法，直接套框架即可，没啥可说的，具体看代码和注释吧。

924. 尽量减少恶意软件的传播

给出了一个由 n 个节点组成的网络，用 n × n 个邻接矩阵图 graph 表示。在节点网络中，当 graph[i][j] = 1 时，表示节点 i 能够直接连接到另一个节点 j。
一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。
假设 M(initial) 是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。
如果从 initial 中移除某一节点能够最小化 M(initial)， 返回该节点。如果有多个节点满足条件，就返回索引最小的节点。
请注意，如果某个节点已从受感染节点的列表 initial 中删除，它以后仍有可能因恶意软件传播而受到感染。
看到这个题，我感觉这个题考察的肯定是图的连通性问题。
按照题目的描述，在同一个连通分量中，只要有一个节点被感染，那么整个连通分量中的所有节点最终都会被感染。
题目让我们删除一个初始感染节点，使得最终感染的节点数最小，其实就是让我们找一个只有一个节点被感染的连通分量，且这个连通分量中的节点数最多。
只要把这个连通分量中的那个感染节点删掉，就可以减少最多的感染节点数，也就是题目说的最小化 M(initial)。
对于连通性问题，我首先想到的是 Union Find 并查集算法。但仔细想想，这题好像没必要上并查集算法，普通的 DFS/BFS 算法也可以遍历连通分量，而且更简单。
所以这个题可以类比成经典的 岛屿系列题目，如果看过这篇文章，肯定就会用 DFS 的解法来做这个题了。
DFS 的解法留给你参照岛屿题目实现吧，我这里就用 BFS 算法来做这个题。注意题目输入的图是 邻接矩阵形式，你要知道怎么寻找邻居节点。
完整代码如下：
这题还是比较复杂的，bfs 函数带返回值，多理解理解。

2101. 引爆最多的炸弹

给你一个炸弹列表。一个炸弹的 爆炸范围 定义为以炸弹为圆心的一个圆。
炸弹用一个下标从 0 开始的二维整数数组 bombs 表示，其中 bombs[i] = [xi, yi, ri] 。xi 和 yi 表示第 i 个炸弹的 X 和 Y 坐标，ri 表示爆炸范围的 半径 。
你需要选择引爆 一个 炸弹。当这个炸弹被引爆时，所有 在它爆炸范围内的炸弹都会被引爆，这些炸弹会进一步将它们爆炸范围内的其他炸弹引爆。
给你数组 bombs ，请你返回在引爆 一个 炸弹的前提下，最多 能引爆的炸弹数目。
这个题挺有意思的，其实题目输入的就是一幅 有向无权图：在一个点的爆炸半径内部的其他点相当于是它可达的邻居节点，可以画一条有向边。
所以这个题相当于在问，给一幅有向图，你可以任选一个节点开始遍历，请问你最多能够遍历多少个节点？
那么解法也非常简单粗暴了，穷举嘛，尝试把每个点都作为起点进行 BFS/DFS 搜索，看看最多可以有多少个可达节点，也就是题目问的最多的引爆数量。
用 BFS 的代码如下：

542. 01 矩阵

给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
我在第一眼看到这个题目时有两个思路方向：一是 动态规划，二是 BFS 算法。
何以见得可以用动态规划思路解决呢？
首先这是个求最值的问题，而且我感觉 mat[x][y] 离 0 最近的距离肯定能根据它周围元素离 0 最近的距离推算出来。这就说明可以比较容易地得到状态转移方程，那么写出动态规划解法也就没什么困难了。
何以见得可以用 BFS 算法思路解决呢？
因为这题描述的场景让我想到 111. 二叉树的最小深度 这类在二叉树中计算最小距离的题目，以及像 1091. 二进制矩阵中的最短路径 这种计算二维矩阵从左上角到右下角最短距离的题目。
从 0 开始往外扩散即可，其实和动态规划本质上是有点像的。
我这里就使用 BFS 算法来求解吧，套框架就出来了。
代码如下：

417. 太平洋大西洋水流问题

有一个 m × n 的矩形岛屿，与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界，而 “大西洋” 处于大陆的右边界和下边界。
这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ， heights[r][c] 表示坐标 (r, c) 上单元格 高于海平面的高度 。
岛上雨水较多，如果相邻单元格的高度 小于或等于 当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。
返回网格坐标 result 的 2D 列表 ，其中 result[i] = [ri, ci] 表示雨水从单元格 (ri, ci) 流动 既可流向太平洋也可流向大西洋 。
notion image
这个题我首先想到的就是纯暴力穷举：题目问哪些格子可以同时流入太平洋和大西洋，那么我就写一个嵌套 for 循环穷举每个格子，然后以每个格子为起点进行 BFS 或 DFS 暴力搜索，看看能否到达太平洋和大西洋。
这个解法虽然非常暴力，但也是可以优化的。
想要优化效率，思路也很简单，要么就是消除重复计算，要么就是充分利用信息。
比方说我如果确定 (i, j) 是可以同时到达太平洋和大西洋的格子，那么其他格子在暴力穷举时，如果能够走到 (i, j)，那么它们也一定可以同时到达太平洋和大西洋。这就类似于备忘录剪枝，可以一定程度提高算法效率。这属于消除重复计算。
我们使用另一种更巧妙的方法：
对于这道题，显然最左侧、最上侧的格子一定可以流入太平洋，最右侧、最下侧的格子一定可以流入大西洋，这个信息可以充分利用起来。
比方说，我可以把以最左侧、最上侧的格子为起点向内陆进行反向搜索，就可以很容易地算出来哪些格子可以流入太平洋；同理，我也可以把以最右侧、最下侧的格子为起点向内陆进行反向搜索，就可以很容易地算出来哪些格子可以流入大西洋。
综合上面两个搜索结果，就可以筛选出来哪些格子可以同时流入太平洋和大西洋了。
这个思路进行两次时间复杂度是 O(MN) 的 BFS/DFS 搜索，所以总的时间复杂度还是 O(MN)，比一开始的暴力穷举要高效。
我这里就用 BFS 来实现这个思路吧，DFS 也是一样的，你可以自己尝试一下。
代码如下：
❗ 问题出在这两行：
这两行代码 看起来 是在创建一个 m x n 的二维布尔数组，但实际上它们创建的是 多个引用指向同一个子列表，也就是说：
这会导致你修改 visitedP[i][j] 时，其他行的同一列也会被修改，从而引发错误的访问标记，最终导致错误的结果。
✅ 正确的写法应该是：
或者更简洁地写成：
这样可以确保每一行都是独立的列表，互不影响。

365. 水壶问题

有两个水壶，容量分别为 x 和 y 升。水的供应是无限的。确定是否有可能使用这两个壶准确得到 target 升。
你可以：
  • 装满任意一个水壶
  • 清空任意一个水壶
  • 将水从一个水壶倒入另一个水壶，直到接水壶已满，或倒水壶已空。
这道题非常经典，也非常有意思。我没记错的话，我小学就做过类似的数学题，不过那时候也没什么章法，反正不断地倒来倒去肯定能蒙出目标水量。
那么到了现在这个阶段，我们首先想的应该是把问题抽象成树结构，然后穷举所有的倒法，看看是否有可能凑出 targetCapacity。
如果把两个桶中现有的水量作为「状态」，那么题目给出的几种倒水方法就是导致「状态」发生改变的「选择」，这样一来，你完全可以用动态规划思路来做。
同时，你也可以用 BFS 算法框架 来解决这道题。我这里就写 BFS 算法吧，具体细节看代码中的注释。
最后，这道题的最优解法是数学方法，你可以去了解一下「裴蜀定理」，也叫「贝祖定理」，有兴趣的读者可以自行搜索，我这里只给出最通用的计算机算法思路，不展开讲数学方法了。
代码如下：

721. 账户合并

给定一个列表 accounts，每个元素 accounts[i] 是一个字符串列表，其中第一个元素 accounts[i][0] 是 名称 (name)，其余元素是 emails 表示该账户的邮箱地址。
现在，我们想合并这些账户。如果两个账户都有一些共同的邮箱地址，则两个账户必定属于同一个人。请注意，即使两个账户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的账户，但其所有账户都具有相同的名称。
合并账户后，按以下格式返回账户：每个账户的第一个元素是名称，其余元素是 按字符 ASCII 顺序排列 的邮箱地址。账户本身可以以 任意顺序 返回。
只要两个有相同名称，且存在公共的账号，那么就可以合并。
看完题目，我首先想到的是 二分图 结构，即如果把用户名和邮箱看成两类节点存到同一幅图中，那么用户名节点的相邻节点就是邮箱，邮箱节点的相邻节点就是用户名。
但是又仔细想了下，二分图对这道题没啥实际作用，还不如用最简单的 HashMap 来存储用户和邮箱的关系。
因为人可能重名，但邮箱不会重复，所以我就想了一个简单的解法，把邮箱作为 key，accounts 的索引作为 value，这样就可以很方便地找到所有包含某个邮箱的账户。
然后我遍历这些账户，把所有的邮箱放到一个 HashSet 中去个重，最后排个序，不就得到合并后的账户了吗？题目又说同一个人不会有不同的名字，所以合并的这些邮箱对应的用户名肯定也都是一样的。
但实际上是错的。错误地原因在于，只考虑了一层关联关系。
比方说，email1 和 email1.1, email1.2, email1.3 共同出现过，那么我可以确定 email1, email1.1, email1.2, email1.3 是同一个人的邮。
但如果 email1.2 又和 email1.2.1, email1.2.2 共同出现过，那么实际上这个人的邮箱应该是 email1, email1.1, email1.2, email1.2.1, email1.2.2, email1.3。
所以看到没有，邮箱间的关联关系不是简单的线性结构，而是树结构，所以需要 DFS/BFS 算法来穷举。
我这里就使用 BFS 算法吧，代码如下：
算法过程如下：
  • 把邮箱看作图中的节点
  • 如果两个邮箱出现在同一个账户中，就在它们之间连一条边
  • 然后用 BFS 找出所有连通的邮箱集合（即属于同一个人的邮箱）
  • 最后将这些邮箱集合合并成一个账户