正文
4、例题
（1）二叉树的层序遍历 | leetcode102
给定二叉树的根节点，返回节点值的层序遍历
class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { // 特判 vector<vector<int>> ans; if (!root) { return ans; } // 初始化队列 queue <TreeNode*> q; q.push(root); // 每次取出队列中的所有节点进行处理 // 然后把这些节点的左右节点加入队列 // 直至队列为空时结束 while (!q.empty()) { ans.push_back(vector<int>()); int num = q.size(); while (num-- > 0) { // 当前元素出队 TreeNode* node = q.front(); q.pop(); // 当前元素加入结果 ans.back().push_back(node -> val); // 相邻元素入队 if (node -> left ) { q.push(node -> left ); } if (node -> right) { q.push(node -> right); } } } // 返回结果 return ans; } };
（2）二叉树的最小深度 | leetcode111
给定二叉树的根节点，返回最小深度，最小深度是从根节点到最近叶子节点的最短路径上的节点数量
class Solution { public: int minDepth(TreeNode* root) { // 特判 if (!root) { return 0; } // 初始化步数 int step = 1; // 初始化队列 queue <TreeNode*> q; q.push(root); // 每次取出队列中的所有节点进行处理 // 然后把这些节点的左右节点加入队列 while (!q.empty()) { int num = q.size(); while (num-- > 0) { // 当前元素出队 TreeNode* node = q.front(); q.pop(); // 如果满足结束条件，即到达叶节点 // 那么返回对应结果 if ( node -> left == nullptr && node -> right == nullptr ) { return step; } // 相邻元素入队 if (node -> left ) { q.push(node -> left ); } if (node -> right) { q.push(node -> right); } } // 步数加一 step++; } return -1; } };
（3）二叉树的右侧视图 | leetcode199
给定二叉树的根节点，想象自己站在树的右侧，按照从顶部到底部的顺序，返回从右侧看到的节点值
class Solution { public: vector<int> rightSideView(TreeNode* root) { // 特判 vector<int> ans; if (!root) { return ans; } // 初始化队列 queue <TreeNode*> q; q.push(root); // 每次取出队列中的所有节点进行处理 // 然后把这些节点的左右节点加入队列 // 直至队列为空时结束 while (!q.empty()) { int num = q.size(); while (num-- > 0) { // 当前元素出队 TreeNode* node = q.front(); q.pop(); // 如果当前节点符合要求，即该节点为最右侧节点 // 那么将该节点加入结果 if (num == 0) { ans.push_back(node -> val); } // 相邻元素入队 if (node -> left ) { q.push(node -> left ); } if (node -> right) { q.push(node -> right); } } } // 返回结果 return ans; } };
（4）围绕的区域 | leetcode130
给定一个 m × n 字符矩阵，由字符 X 和 O 组成，找到所有被 X 围绕的 O，并且将这些 O 转变成 X
基本思路：
题目中说，任何边界上的 O 都不会填充为 X，因为这些 O 没有被 X 所围绕
换句话说，与边界相连的 O 都继续保持为 O，而其它的 O 则会被 X 所填充
解题思路：
找出边界上的 O
找出与上述的 O 相连的 O
将上述找到的 O 填充为 A
遍历矩阵，将 O 修改为 X，将 A 修改为 O
注意：
上述的第二步，既可以使用深度优先搜索实现，也可以使用广度优先搜索实现
另外，本题可通过直接修改数组作为访问标志，因此无需额外的哈希集合记录
// 广度优先搜索 class Solution { public: const int dx[4] = {1, -1, 0, 0}; const int dy[4] = {0, 0, 1, -1}; void bfs(vector<vector<char>>& board, int x, int y, int m, int n) { // 特判 if (board[x][y] != 'O') { return; } // 初始化队列 queue<pair<int, int>> q; q.emplace(x, y); board[x][y] = 'A'; // 依次取出队列中的节点进行处理 // 把这些节点的相邻节点加入队列 // 直至队列为空时结束 while (!q.empty()) { // 当前元素出队 int ax = q.front().first; int ay = q.front().second; q.pop(); // 相邻元素入队 for (int k = 0; k < 4; k++) { int bx = ax + dx[k]; int by = ay + dy[k]; // 判断相邻元素是否合法 if ( bx < 0 || by < 0 || bx >= m || by >= n || board[bx][by] != 'O' ) { continue; } // 如果相邻元素合法，则入队 q.emplace(bx, by); board[bx][by] = 'A'; } } } void solve(vector<vector<char>>& board) { // 特判 int m = board.size(); if (m <= 2) { return; } int n = board[0].size(); if (n <= 2) { return; } // 1. 找出边界上的 'O' // 2. 找出与上述的 'O' 相连的 'O' (广度优先搜索) // 3. 将上述找到的 'O' 填充为 'A' for (int i = 1; i <= m - 2; i++) { bfs(board, i, 0, m, n); bfs(board, i, n - 1, m, n); } for (int j = 0; j <= n - 1; j++) { bfs(board, 0, j, m, n); bfs(board, m - 1, j, m, n); } // 4. 遍历矩阵，将 'O' 修改为 'X'，将 'A' 修改为 'O' for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (board[i][j] == 'O') { board[i][j] = 'X'; } if (board[i][j] == 'A') { board[i][j] = 'O'; } } } } };
// 深度优先搜索 class Solution { public: void dfs(vector<vector<char>>& board, int x, int y, int m, int n) { if ( x < 0 || y < 0 || x >= m || y >= n || board[x][y] != 'O' ) { return; } board[x][y] = 'A'; dfs(board, x + 1, y, m, n); dfs(board, x - 1, y, m, n); dfs(board, x, y + 1, m, n); dfs(board, x, y - 1, m, n); } void solve(vector<vector<char>>& board) { // 特判 int m = board.size(); if (m <= 2) { return; } int n = board[0].size(); if (n <= 2) { return; } // 1. 找出边界上的 'O' // 2. 找出与上述的 'O' 相连的 'O' (深度优先搜索) // 3. 将上述找到的 'O' 填充为 'A' for (int i = 1; i <= m - 2; i++) { dfs(board, i, 0, m, n); dfs(board, i, n - 1, m, n); } for (int j = 0; j <= n - 1; j++) { dfs(board, 0, j, m, n); dfs(board, m - 1, j, m, n); } // 4. 遍历矩阵，将 'O' 修改为 'X'，将 'A' 修改为 'O' for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (board[i][j] == 'O') { board[i][j] = 'X'; } if (board[i][j] == 'A') { board[i][j] = 'O'; } } } } };
（5）岛屿的数量 | leetcode200
给定一个 m × n 数字矩阵，由数字 0 和 1 组成，找到所有被 0 围绕的 1，并统计数量
// 广度优先搜索 class Solution { public: const int dx[4] = {1, -1, 0, 0}; const int dy[4] = {0, 0, 1, -1}; void bfs(vector<vector<char>>& grid, int x, int y, int m, int n) { // 初始化队列 queue<pair<int, int>> q; q.emplace(x, y); grid[x][y] = '0'; // 依次取出队列中的节点进行处理 // 把这些节点的相邻节点加入队列 // 直至队列为空时结束 while (!q.empty()) { // 当前元素出队 int ax = q.front().first; int ay = q.front().second; q.pop(); // 相邻元素入队 for (int k = 0; k < 4; k++) { int bx = ax + dx[k]; int by = ay + dy[k]; // 判断相邻元素是否合法 if ( bx < 0 || by < 0 || bx >= m || by >= n || grid[bx][by] != '1' ) { continue; } // 如果相邻元素合法，则入队 q.emplace(bx, by); grid[bx][by] = '0'; } } } int numIslands(vector<vector<char>>& grid) { int m = grid.size(); int n = grid[0].size(); // 遍历矩阵 // 发现陆地之后，岛屿数量加一，并使用广度优先搜索将相邻的陆地标记 int ans = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == '1') { ans += 1; bfs(grid, i, j, m, n); } } } return ans; } };
// 深度优先搜索 class Solution { public: void dfs(vector<vector<char>>& grid, int x, int y, int m, int n) { if ( x < 0 || y < 0 || x >= m || y >= n || grid[x][y] != '1' ) { return; } grid[x][y] = '0'; dfs(grid, x + 1, y, m, n); dfs(grid, x - 1, y, m, n); dfs(grid, x, y + 1, m, n); dfs(grid, x, y - 1, m, n); } int numIslands(vector<vector<char>>& grid) { int m = grid.size(); int n = grid[0].size(); // 遍历矩阵 // 发现陆地之后，岛屿数量加一，并使用深度优先搜索将相邻的陆地标记 int ans = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == '1') { ans += 1; dfs(grid, i, j, m, n); } } } return ans; } };
（6）打开转盘锁 | leetcode752
实际应用场景下的广度优先搜索，本质上是对字符串进行遍历
关键是找到当前节点的相邻节点，以及定义清楚元素要满足的约束条件
class Solution { public: int openLock(vector<string>& deadends, string target) { // 初始化步数 int step = 0; // 初始化队列 queue <string> q; q.push("0000"); // 初始化集合 unordered_set <string> deadeds {deadends.begin(), deadends.end()}; unordered_set <string> visited {"0000"}; // 初始化辅助函数 auto addOne = [](char x) -> char { return (x == '9' ? '0' : x + 1); }; auto subOne = [](char x) -> char { return (x == '0' ? '9' : x - 1); }; // 每次取出队列中的所有节点进行处理 // 然后把这些节点的相邻节点加入队列 // 直至队列为空时结束 while (!q.empty()) { int num = q.size(); while (num-- > 0) { // 当前元素出队 string str = q.front(); q.pop(); // 若元素不满足约束条件 // 跳过当前元素 if (deadeds.find(str) != deadeds.end()) { continue; } // 若元素能满足结束条件 // 返回对应结果 if (str == target) { return step; } // 相邻元素入队 char chr; for (int i = 0; i < 4; i++) { // 备份 chr = str[i]; // 第 i 个字符加 1 得到相邻元素，如果相邻元素合法，将其加入队列 str[i] = addOne(chr); if (visited.find(str) == visited.end()) { q.push(str); visited.insert(str); } // 第 i 个字符减 1 得到相邻元素，如果相邻元素合法，将其加入队列 str[i] = subOne(chr); if (visited.find(str) == visited.end()) { q.push(str); visited.insert(str); } // 还原 str[i] = chr; } } // 步数加一 step++; } // 遍历完没找到目标 return -1; } };
（7）解滑动谜题 | leetcode773
咋一看是二维数组的广度优先搜索，实际上可以将其转化为字符串形式，本质上与例题六相似
解题的关键在于预处理，一是将二维数组转字符串，二是找到找到当前节点的相邻节点
class Solution { public: int slidingPuzzle(vector<vector<int>>& board) { // 预处理 string target = "123450"; int m = board.size(); int n = board[0].size(); string input; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { input += char(board[i][j] + '0'); } } vector<vector<int>> neighbors = {{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}}; // 初始化步数 int step = 0; // 初始化队列 queue <string> q; q.push(input); // 初始化集合 unordered_set <string> visited; visited.insert(input); // 每次取出队列中的所有节点进行处理 // 然后把这些节点的相邻节点加入队列 // 直至队列为空时结束 while (!q.empty()) { int num = q.size(); while (num-- > 0) { // 当前元素出队 string str = q.front(); q.pop(); // 若元素能满足结束条件 // 返回对应结果 if (str == target) { return step; } // 相邻元素入队 int x = str.find('0'); for (int y: neighbors[x]) { // 交换 // 得到相邻元素 swap(str[x], str[y]); // 如果相邻元素合法 // 将其加入队列 if (visited.find(str) == visited.end()) { q.push(str); visited.insert(str); } // 还原 swap(str[x], str[y]); } } // 步数加一 step++; } // 遍历完没找到目标 return -1; } };
8）单词接龙 | leetcode127
本质上也是字符串的遍历，与例题六相似，只不过增加了遍历的约束
class Solution { public: int ladderLength(string beginWord, string endWord, vector<string>& wordList) { // 初始化步数 int step = 1; // 初始化队列 queue <string> q; q.push(beginWord); // 初始化集合 unordered_set<string> words {wordList.begin(), wordList.end()}; // 每次取出队列中的所有节点进行处理 // 然后把这些节点的相邻节点加入队列 // 直至队列为空时结束 while (!q.empty()) { int num = q.size(); while (num-- > 0) { // 当前元素出队 string str = q.front(); q.pop(); // 若元素能满足结束条件 // 返回对应结果 if (str == endWord) { return step; } // 相邻元素入队 char b; for (int i = 0; i < str.size(); i++) { // 备份 b = str[i]; // 第 i 个字符修改为 a-z 得到相邻元素，如果相邻元素合法，将其加入队列 for (char c = 'a'; c <= 'z'; c++) { str[i] = c; if (words.find(str) != words.end()) { q.push(str); words.erase(str); } } // 还原 str[i] = b; } } // 步数加一 step++; } // 遍历完没找到目标 return 0; } };
5、优化
广度优先搜索还有一个常用的优化方法，那就是双向广度优先搜索
一般的广度优先搜索是从初始节点开始向周围扩散，直至遇到目标节点或满足结束条件时停止
而双向广度优先搜索是从初始节点和目标节点同时开始扩散，直至两者出现交集时停止
根据上面的描述，相信大家也能发现，双向广度优先搜索有其使用限制，那就是必须知道目标节点
如果一开始不知道目标节点，那么就无法使用这个优化方法
为什么双向广度优先搜索更好呢？或者说在什么场景下能够表现更好呢？
随着扩散步数的增加，所维护的节点集合也会随之增大，在这种情况下使用双向广度优先搜索更佳
双向广度优先搜索通过交替扩散初始节点和目标节点以减少维护的节点数量，大家看下图就能理解
实现上，双向广度优先搜索使用两个哈希集合分别维护两个从初始节点和目标节点扩散的节点集合
为什么不再使用队列了呢？这是为了方便判断两个节点集合是否存在交集
而在扩散两个节点集合时，可以选择每次扩散小的集合，而非轮流扩散，这也是一个小的优化策略
这里还是以例题六为例，给出双向广度优先搜索的代码
class Solution { public: int openLock(vector<string>& deadends, string target) { // 初始化步数 int step = 0; // 初始化队列 // 改为用集合，方便判断是否有交集 unordered_set <string> q1 {"0000"}; unordered_set <string> q2 {target}; // 初始化集合 unordered_set <string> deadeds {deadends.begin(), deadends.end()}; unordered_set <string> visited; // 初始化辅助函数 auto addOne = [](char x) -> char { return (x == '9' ? '0' : x + 1); }; auto subOne = [](char x) -> char { return (x == '0' ? '9' : x - 1); }; // 每次取出队列中的所有节点进行处理 // 然后把这些节点的相邻节点加入队列 // 直至队列为空时结束 while ( !q1.empty() && !q2.empty() ) { // 构造临时集合 unordered_set <string> q0; // 扩散小的集合 if (q1.size() > q2.size()) { unordered_set <string> q3 = q1; q1 = q2; q2 = q3; } // 取出当前元素 for (string str: q1) { // 若元素不满足约束条件 // 跳过当前元素 if (deadeds.find(str) != deadeds.end()) { continue; } // 若元素能满足结束条件 // 返回对应结果 if (q2.find(str) != q2.end()) { return step; } // 更新集合 visited.insert(str); // 相邻元素入队 char chr; for (int i = 0; i < 4; i++) { // 备份 chr = str[i]; // 第 i 个字符加 1 得到相邻元素，如果相邻元素合法，将其加入队列 str[i] = addOne(chr); if (visited.find(str) == visited.end()) { q0.insert(str); } // 第 i 个字符减 1 得到相邻元素，如果相邻元素合法，将其加入队列 str[i] = subOne(chr); if (visited.find(str) == visited.end()) { q0.insert(str); } // 还原 str[i] = chr; } } // 步数加一 step++; } // 遍历完没找到目标 return -1; } };
