[TOC]
BFS 和 DFS
BFS广度有限搜索和DFS深度优先搜索算法是特别常用的两种算法
DFS 算法就是回溯算法，DFS 遍历使用递归：
写 BFS 算法都是用「队列」这种数据结构，每次将一个节点周围的所有节点加入队列。BFS 遍历使用队列数据结构。BFS解决最短路径
Leetcode
111. 二叉树的最小深度【简单/BFS/DFS】
// ============== 解法一： BFS 迭代实现，广度优先遍历 ================
// https://www.cnblogs.com/Lusai/p/15709094.html
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func minDepth(root *TreeNode) int {
if root == nil {
return 0
}
queue :=[]*TreeNode{root} // 查找队列,将起点加入队列
depth := 1 // root 本身就是一层，depth初始化为1
for len(queue)!=0{
size := len(queue)
// 将当前队列中的所有结点向四周扩散
for i := 0; i < size; i++ {
cur := queue[0]
// 判断是否到终点
if cur.Left == nil && cur.Right == nil {
return depth
}
// 将 cur的相邻节点加入队列
if cur.Left != nil {
queue = append(queue, cur.Left)
}
if cur.Right != nil {
queue = append(queue, cur.Right)
}
// 去掉当前节点
queue = queue[1:]
}
// 这里增加深度
depth++
}
return depth
}
// ============== 解法二： DFS ================
func minDepth(root *TreeNode) int {
if root == nil {
return 0
}
if root.Left != nil && root.Right == nil {
return 1 + minDepth(root.Left)
}
if root.Right != nil && root.Left == nil {
return 1 + minDepth(root.Right)
}
return 1 + Min(minDepth(root.Left), minDepth(root.Right))
}
102. 二叉树的层序遍历【中等】
https://leetcode-cn.com/problems/binary-tree-level-order-traversal/solution/bfs-de-shi-yong-chang-jing-zong-jie-ceng-xu-bian-l/
package main
import "fmt"
func main() {
/*
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
*/
TreeNode1 := TreeNode{
Val: 2,
Left: &TreeNode{9, nil, nil},
Right: &TreeNode{20, &TreeNode{15, nil, nil}, &TreeNode{7, nil, nil}},
}
fmt.Println(levelOrder(&TreeNode1))
}
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
// ============== 解法一： BFS 迭代实现，广度优先遍历 ================
func levelOrder(root *TreeNode) (res [][]int) {
if root == nil {
return res
}
queue := []*TreeNode{root}
for len(queue) != 0 {
size := len(queue)
var curLevel []int
for i := 0; i < size; i++ {
node := queue[0]
curLevel = append(curLevel, node.Val)
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
queue = queue[1:]
}
res = append(res, curLevel)
}
return res
}
127. 单词接龙【困难】
// // ============== 解法一： BFS 迭代实现，广度优先遍历 ================
//https://leetcode-cn.com/problems/word-ladder/solution/shou-hua-tu-jie-127-dan-ci-jie-long-bfsde-dian-x-2/
func ladderLength(beginWord string, endWord string, wordList []string) int {
wordMap := map[string]bool{}
for _, w := range wordList {
wordMap[w] = true
}
queue := []string{beginWord}
level := 1
for len(queue) != 0 {
levelSize := len(queue)
for i := 0; i < levelSize; i++ {
word := queue[0]
if word == endWord {
return level
}
for c := 0; c < len(word); c++ {
for j := 'a'; j <= 'z'; j++ {
newWord := word[:c] + string(j) + word[c+1:]
if wordMap[newWord] == true {
queue = append(queue, newWord)
delete(wordMap, newWord)
}
}
}
queue = queue[1:]
}
level++
}
return 0
}
// // // ============== 解法二： 双向BFS 迭代实现 ================
//https://leetcode-cn.com/problems/word-ladder/solution/golang-shi-xian-de-shuang-xiang-bfs-by-themoonston/
490. 迷宫【会员/中等/BFS】
由空地（用 0 表示）和墙（用 1 表示）组成的迷宫 maze 中有一个球。球可以途经空地向 上、下、左、右 四个方向滚动，且在遇到墙壁前不会停止滚动。当球停下时，可以选择向下一个方向滚动。
给你一个大小为 m x n 的迷宫 maze ，以及球的初始位置 start 和目的地 destination ，其中 start = [startrow, startcol] 且 destination = [destinationrow, destinationcol] 。请你判断球能否在目的地停下：如果可以，返回 true ；否则，返回 false 。
输入：maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]
输出：true
解释：一种可能的路径是 : 左 -> 下 -> 左 -> 下 -> 右 -> 下 -> 右。
输入：maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [3,2]
输出：false
解释：不存在能够使球停在目的地的路径。注意，球可以经过目的地，但无法在那里停驻。
你可以 假定迷宫的边缘都是墙壁（参考示例）。
https://leetcode-cn.com/problems/the-maze/solution/golangding-dao-tou-de-cai-shi-lin-ju-by-bloodborne/
func main() {
maze := [][]int{{0, 0, 1, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 1, 0}, {1, 1, 0, 1, 1}, {0, 0, 0, 0, 0}}
start := []int{0, 4}
destination := []int{4, 4}
fmt.Println(hasPath(maze, start, destination))
}
func hasPath(maze [][]int, start []int, destination []int) bool {
queue := [][]int{start}
rowNum, colNow := len(maze), len(maze[0]) // row表示行，col表示列
// 创建一个rowNum*colNum 的二维数组
visited := make([][]bool, rowNum)
for i := 0; i < rowNum; i++ {
visited[i] = make([]bool, colNow)
}
visited[start[0]][start[1]] = true
dir := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}} // 上下左右
for len(queue) != 0 {
top := queue[0]
fmt.Println("top is %+v", top)
if top[0] == destination[0] && top[1] == destination[1] { // 遇到终点返回true
return true
}
for _, v := range dir {
newRow, newCol := top[0]+v[0], top[1]+v[1]
// 冲到方向最深处
for newRow >= 0 && newRow < rowNum && newCol >= 0 && newCol < colNow && maze[newRow][newCol] == 0 {
newRow += v[0]
newCol += v[1]
}
newRow -= v[0]
newCol -= v[1]
if visited[newRow][newCol] {
continue
}
queue = append(queue, []int{newRow, newCol})
fmt.Println("queue is %+v", queue)
visited[newRow][newCol] = true
}
queue = queue[1:]
}
return false
}
505. 迷宫 II【会员/中等/BFS】
输入 1: 迷宫由以下二维数组表示
0 0 1 0 0
0 0 0 0 0
0 0 0 1 0
1 1 0 1 1
0 0 0 0 0
输入 2: 起始位置坐标 (rowStart, colStart) = (0, 4)
输入 3: 目的地坐标 (rowDest, colDest) = (4, 4)
输出: 12
// 有点难度了
func shortestDistance(maze [][]int, start []int, destination []int) int {
queue, rowNum, colNow := [][]int{start}, len(maze), len(maze[0])
stepCount := make([][]int, rowNum)
for i := 0; i < rowNum; i++ {
stepCount[i] = make([]int, colNow)
for j := 0; j < colNow; j++ {
stepCount[i][j] = -1
}
}
stepCount[start[0]][start[1]] = 0
dir := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}} // 上下左右
for len(queue) != 0 {
top := queue[0]
for _, v := range dir {
newRow, newCol := top[0]+v[0], top[1]+v[1]
step := 0
for newRow >= 0 && newRow < rowNum && newCol >= 0 && newCol < colNow && maze[newRow][newCol] == 0 {
newRow, newCol = newRow+v[0], newCol+v[1]
step++
}
newRow, newCol = newRow-v[0], newCol-v[1]
if stepCount[newRow][newCol] != -1 && stepCount[top[0]][top[1]]+step >= stepCount[newRow][newCol] {
continue
}
queue = append(queue, []int{newRow, newCol})
stepCount[newRow][newCol] = stepCount[top[0]][top[1]] + step
}
queue = queue[1:]
}
return stepCount[destination[0]][destination[1]]
}
207. 课程表【中等/拓扑排序】
https://leetcode-cn.com/problems/course-schedule/solution/go-jian-dan-jie-fa-dfs-bfs-by-xilepeng-vhid/
210. 课程表 II【中等/拓扑排序】
2174. Remove All Ones With Row and Column Flips II（会员/中等/状态压缩/BFS/DFS）
317. 离建筑物最近的距离（会员/困难/BFS/做一下）
给你一个 m × n 的网格，值为 0 、 1 或 2 ，其中:
每一个 0 代表一块你可以自由通过的 空地
每一个 1 代表一个你不能通过的 建筑
每个 2 标记一个你不能通过的 障碍
你想要在一块空地上建造一所房子，在 最短的总旅行距离 内到达所有的建筑。你只能上下左右移动。
返回到该房子的 最短旅行距离 。如果根据上述规则无法建造这样的房子，则返回 -1 。
总旅行距离 是朋友们家到聚会地点的距离之和。
使用 曼哈顿距离 计算距离，其中距离 (p1, p2) = |p2.x - p1.x | + | p2.y - p1.y | 。
输入：grid = [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]
输出：7
解析：给定三个建筑物 (0,0)、(0,4) 和 (2,2) 以及一个位于 (0,2) 的障碍物。
由于总距离之和 3+3+1=7 最优，所以位置 (1,2) 是符合要求的最优地点。
故返回7。
314. 二叉树的垂直遍历（会员/中等/BFS）
给你一个二叉树的根结点，返回其结点按 垂直方向（从上到下，逐列）遍历的结果。
如果两个结点在同一行和列，那么顺序则为 从左到右。
输入：root = [3,9,20,null,null,15,7]
输出：[[9],[3,15],[20],[7]]
输入：root = [3,9,8,4,0,1,7]
输出：[[4],[9],[3,0,1],[8],[7]]
输入：root = [3,9,8,4,0,1,7,null,null,null,2,5]
输出：[[4],[9,5],[3,0,1],[8,2],[7]]
286. 墙与门（会员/中等/BFS）
你被给定一个 m × n 的二维网格 rooms ，网格中有以下三种可能的初始化值：
-1 表示墙或是障碍物
0 表示一扇门
INF 无限表示一个空的房间。然后，我们用 231 - 1 = 2147483647 代表 INF。你可以认为通往门的距离总是小于 2147483647 的。
你要给每个空房间位上填上该房间到 最近门的距离 ，如果无法到达门，则填 INF 即可。
输入：rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]
输出：[[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]
输入：rooms = [[-1]]
输出：[[-1]]
输入：rooms = [[2147483647]]
输出：[[2147483647]]
输入：rooms = [[0]]
输出：[[0]]
742. 二叉树最近的叶节点（会员/中等/BFS/DFS）
给定一个 每个结点的值互不相同 的二叉树，和一个目标整数值 k，返回 树中与目标值 k 最近的叶结点 。
与叶结点最近 表示在二叉树中到达该叶节点需要行进的边数与到达其它叶结点相比最少。而且，当一个结点没有孩子结点时称其为叶结点。
输入：root = [1, 3, 2], k = 1
输出： 2
解释： 2 和 3 都是距离目标 1 最近的叶节点。
输入：root = [1,2,3,4,null,null,null,5,null,6], k = 2
输出：3
解释：值为 3（而不是值为 6）的叶节点是距离结点 2 的最近结点。
1197. 进击的骑士（会员/中等/BFS/DFS）
一个坐标可以从 -infinity 延伸到 +infinity 的 无限大的 棋盘上，你的 骑士 驻扎在坐标为 [0, 0] 的方格里。
骑士的走法和中国象棋中的马相似，走 “日” 字：即先向左（或右）走 1 格，再向上（或下）走 2 格；或先向左（或右）走 2 格，再向上（或下）走 1 格。
每次移动，他都可以按图示八个方向之一前进。
返回 骑士前去征服坐标为 [x, y] 的部落所需的最小移动次数 。本题确保答案是一定存在的。
输入：x = 2, y = 1
输出：1
解释：[0, 0] → [2, 1]
输入：x = 5, y = 5
输出：4
解释：[0, 0] → [2, 1] → [4, 2] → [3, 4] → [5, 5]
694. 不同岛屿的数量（会员/中等/BFS/DFS）
给定一个非空 01 二维数组表示的网格，一个岛屿由四连通（上、下、左、右四个方向）的 1 组成，你可以认为网格的四周被海水包围。
请你计算这个网格中共有多少个形状不同的岛屿。两个岛屿被认为是相同的，当且仅当一个岛屿可以通过平移变换（不可以旋转、翻转）和另一个岛屿重合。
11000
11000
00011
00011
11011
10000
00001
11011
160. 相交链表（简单/BFS/DFS）
235. 二叉搜索树的最近公共祖先（中等/BFS/DFS）
236. 二叉树的最近公共祖先（中等/BFS/DFS）
https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/solution/236-er-cha-shu-de-zui-jin-gong-gong-zu-x-tl5b/
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
if root == nil {
return nil
}
// 如果p,q为根节点，则公共祖先为根节点
if root.Val == p.Val || root.Val == q.Val {
return root
}
// 如果p,q在左子树，则公共祖先在左子树查找
if find(root.Left, p) && find(root.Left, q) {
return lowestCommonAncestor(root.Left, p, q)
}
// 如果p,q在右子树，则公共祖先在右子树查找
if find(root.Right, p) && find(root.Right, q) {
return lowestCommonAncestor(root.Right, p, q)
}
// 如果p,q分属两侧，则公共祖先为根节点
return root
}
func find(root, c *TreeNode) bool {
if root == nil {
return false
}
if root.Val == c.Val {
return true
}
return find(root.Left, c) || find(root.Right, c)
}
======解法二 利用hash表和存储走过的路利用hash表和存储走过的路 ======
https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/solution/by-cogency-dvnb/
https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/solution/zhou-liu-zaoc-by-per-7-5t8u/
/*思路：我们可以用哈希表存储所有节点的父节点，然后我们就可以利用节点的父节点信息从 p 结点开始不断往上跳，并记录已经访问过的节点
，再从 q 节点开始不断往上跳，如果碰到已经访问过的节点，那么这个节点就是我们要找的最近公共祖先。
算法：从根节点开始遍历整棵二叉树，用哈希表记录每个节点的父节点指针。从 p 节点开始不断往它的祖先移动，并用数据结构记录已经访问过的祖先节点。同样，我们再从 q 节点开始不断往它的祖先移动，如果有祖先已经被访问过，即意味着这是 p 和 q 的深度最深的公共祖先，即 LCA节点。*/
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
parent := map[int]*TreeNode{}
visited := map[int]bool{}
var dfs func(*TreeNode)
dfs = func(r *TreeNode) {
if r == nil {
return
}
if r.Left != nil {
parent[r.Left.Val] = r
dfs(r.Left)
}
if r.Right != nil {
parent[r.Right.Val] = r
dfs(r.Right)
}
}
dfs(root)
for p != nil {
visited[p.Val] = true
p = parent[p.Val]
}
for q != nil {
if visited[q.Val] {
return q
}
q = parent[q.Val] // 从q往上找父节点
}
return nil
}
1257. 最小公共区域（会员/中等/BFS/LCA）
给你一些区域列表 regions ，每个列表的第一个区域都包含这个列表内所有其他区域。
很自然地，如果区域 X 包含区域 Y ，那么区域 X 比区域 Y 大。
给定两个区域 region1 和 region2 ，找到同时包含这两个区域的 最小 区域。
如果区域列表中 r1 包含 r2 和 r3 ，那么数据保证 r2 不会包含 r3 。
数据同样保证最小公共区域一定存在。
输入：
regions = [["Earth","North America","South America"],
["North America","United States","Canada"],
["United States","New York","Boston"],
["Canada","Ontario","Quebec"],
["South America","Brazil"]],
region1 = "Quebec",
region2 = "New York"
输出："North America"
最近公共祖先问题（LCA：Lowest common ancestor），指的是在“树”中寻找某两个结点的最近的公共祖先。
https://leetcode.cn/problems/smallest-common-region/solution/javascript-shao-zheng-li-xia-lcawen-ti-de-si-lu-by/
思路：我们可以用哈希表存储所有节点的父节点，然后我们就可以利用节点的父节点信息从 region1 结点开始不断往上跳，并记录已经访问过的节点，再从 region2 节点开始不断往上跳，如果碰到已经访问过的节点，那么这个节点就是我们要找的最近公共祖先。
func findSmallestRegion(regions [][]string, region1 string, region2 string) string {
parent := make(map[string]string)
visited := make(map[string]bool)
row, _ := len(regions), len(regions[0])
for i := 0; i < row; i++ {
for j := 0; j < len(regions[i]); j++ {
if j == 0 { // 很重要，这里必须要把根节点去了
continue
}
parent[regions[i][j]] = regions[i][0]
}
}
// fmt.Println(parent)
for region1 != "" { // 这里为啥是!=" 呢，因为最上的根节点earth没有父节点，他的父节点就是”“
visited[region1] = true
region1 = parent[region1]
}
for region2 != "" {
if visited[region2] {
return region2
}
region2 = parent[region2] // 从q往上找父节点
}
return ""
}
1273. 删除树节点（会员/中等/BFS/DFS）
给你一棵以节点 0 为根节点的树，定义如下：
节点的总数为 nodes 个；
第 i 个节点的值为 value[i] ；
第 i 个节点的父节点是 parent[i] 。
请你删除节点值之和为 0 的每一棵子树。
在完成所有删除之后，返回树中剩余节点的数目。
输入：nodes = 7, parent = [-1,0,0,1,2,2,2], value = [1,-2,4,0,-2,-1,-1]
输出：2
输入：nodes = 7, parent = [-1,0,0,1,2,2,2], value = [1,-2,4,0,-2,-1,-2]
输出：6
输入：nodes = 5, parent = [-1,0,1,0,0], value = [-672,441,18,728,378]
输出：5
输入：nodes = 5, parent = [-1,0,0,1,1], value = [-686,-842,616,-739,-746]
输出：5
1602. 找到二叉树中最近的右侧节点 （会员/中等/BFS/DFS）
1730. 获取食物的最短路径（会员/中等/BFS/DFS）(做一下)
你现在很饿，想要尽快找东西吃。你需要找到最短的路径到达一个食物所在的格子。
给定一个 m x n 的字符矩阵 grid ，包含下列不同类型的格子：
'*' 是你的位置。矩阵中有且只有一个 '*' 格子。
'#' 是食物。矩阵中可能存在多个食物。
'O' 是空地，你可以穿过这些格子。
'X' 是障碍，你不可以穿过这些格子。
返回你到任意食物的最短路径的长度。如果不存在你到任意食物的路径，返回 -1。
输入： grid = [["X","X","X","X","X","X"],["X","*","O","O","O","X"],["X","O","O","#","O","X"],["X","X","X","X","X","X"]]
输出： 3
解释： 要拿到食物，你需要走 3 步。
输入： grid = [["X","X","X","X","X"],["X","*","X","O","X"],["X","O","X","#","X"],["X","X","X","X","X"]]
输出： -1
解释： 你不可能拿到食物。
输入: grid = [["X","X","X","X","X","X","X","X"],["X","*","O","X","O","#","O","X"],["X","O","O","X","O","O","X","X"],["X","O","O","O","O","#","O","X"],["X","X","X","X","X","X","X","X"]]
输出: 6
解释: 这里有多个食物。拿到下边的食物仅需走 6 步。
