BFS DFS 解题模板

利用二叉树解释BFS和DFS的基本算法

Posted by Jeremy Song on 2022-04-06
Estimated Reading Time 3 Minutes
Words 693 In Total
Viewed Times

今天在网上看到了两篇关于DFS和BFS的讲解,文章很不错。刚好最近也在学习BFS和DFS的算法。这里就把两篇文章中的解题模板摘抄出来了。

因为我个人的需要,这里仅仅展示解题模板,不做过多的讲解。文章是人家的,我就不做过多的搬运了。有兴趣的朋友可以在文章末尾点击链接查看原文。


二叉树DFS遍历

1
2
3
4
5
6
7
void dfs(TreeNode root){
if (root == null) {
return;
}
dfs(root.left);
dfs(root.right);
}

二叉树BFS遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
void bfs(TreeNode root) {
Queue<TreeNode> queue = new ArrayDeque<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll(); // Java 的 pop 写作 poll()
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}

二叉树BFS层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void bfs(TreeNode root) {
Queue<TreeNode> queue = new ArrayDeque<>();
queue.add(root);
while (!queue.isEmpty()) {
int n = queue.size();
for (int i = 0; i < n; i++) {
// 变量 i 无实际意义,只是为了循环 n 次
TreeNode node = queue.poll();
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void bfs(TreeNode root) {
Queue<TreeNode> queue = new ArrayDeque<>();
queue.add(root);
while (!queue.isEmpty()) {
Queue<TreeNode> nextQueue = new ArrayDeque<>();
while(!queue.isEmpty()) {
// 变量 i 无实际意义,只是为了循环 n 次
TreeNode node = queue.poll();
if (node.left != null) {
nextQueue.add(node.left);
}
if (node.right != null) {
nextQueue.add(node.right);
}
}
queue.addAll(nextQueue);
}
}

网格 DFS 遍历的框架代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void dfs(int[][] grid, int r, int c) {
// 判断 base case
// 如果坐标 (r, c) 超出了网格范围,直接返回
if (!inArea(grid, r, c)) {
return;
}
// 访问上、下、左、右四个相邻结点
dfs(grid, r - 1, c);
dfs(grid, r + 1, c);
dfs(grid, r, c - 1);
dfs(grid, r, c + 1);
}

// 判断坐标 (r, c) 是否在网格中
boolean inArea(int[][] grid, int r, int c) {
return 0 <= r && r < grid.length
&& 0 <= c && c < grid[0].length;
}

加入避免重复遍历的语句

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void dfs(int[][] grid, int r, int c) {
// 判断 base case
if (!inArea(grid, r, c)) {
return;
}
// 如果这个格子不是岛屿,直接返回
if (grid[r][c] != 1) {
return;
}
grid[r][c] = 2; // 将格子标记为「已遍历过」

// 访问上、下、左、右四个相邻结点
dfs(grid, r - 1, c);
dfs(grid, r + 1, c);
dfs(grid, r, c - 1);
dfs(grid, r, c + 1);
}

// 判断坐标 (r, c) 是否在网格中
boolean inArea(int[][] grid, int r, int c) {
return 0 <= r && r < grid.length
&& 0 <= c && c < grid[0].length;
}

参考资料


欢迎关注我的公众号 须弥零一,跟我一起学习IT知识。


如果您喜欢此博客或发现它对您有用,则欢迎对此发表评论。 也欢迎您共享此博客,以便更多人可以参与。 如果博客中使用的图像侵犯了您的版权,请与作者联系以将其删除。 谢谢 !