[TOC]
BFS 和 DFS
BFS廣度有限搜索和DFS深度優(yōu)先搜索算法是特別常用的兩種算法
DFS 算法就是回溯算法，DFS 遍歷使用遞歸：
寫 BFS 算法都是用「隊(duì)列」這種數(shù)據(jù)結(jié)構(gòu)，每次將一個(gè)節(jié)點(diǎn)周圍的所有節(jié)點(diǎn)加入隊(duì)列。BFS 遍歷使用隊(duì)列數(shù)據(jù)結(jié)構(gòu)。BFS解決最短路徑
Leetcode
111. 二叉樹的最小深度【簡(jiǎn)單/BFS/DFS】
// ============== 解法一： BFS 迭代實(shí)現(xiàn)，廣度優(yōu)先遍歷 ================
// 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} // 查找隊(duì)列,將起點(diǎn)加入隊(duì)列
depth := 1 // root 本身就是一層，depth初始化為1
for len(queue)!=0{
size := len(queue)
// 將當(dāng)前隊(duì)列中的所有結(jié)點(diǎn)向四周擴(kuò)散
for i := 0; i < size; i++ {
cur := queue[0]
// 判斷是否到終點(diǎn)
if cur.Left == nil && cur.Right == nil {
return depth
}
// 將 cur的相鄰節(jié)點(diǎn)加入隊(duì)列
if cur.Left != nil {
queue = append(queue, cur.Left)
}
if cur.Right != nil {
queue = append(queue, cur.Right)
}
// 去掉當(dāng)前節(jié)點(diǎn)
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 迭代實(shí)現(xiàn)，廣度優(yōu)先遍歷 ================
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 迭代實(shí)現(xiàn)，廣度優(yōu)先遍歷 ================
//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 迭代實(shí)現(xiàn) ================
//https://leetcode-cn.com/problems/word-ladder/solution/golang-shi-xian-de-shuang-xiang-bfs-by-themoonston/
490. 迷宮【會(huì)員/中等/BFS】
由空地（用 0 表示）和墻（用 1 表示）組成的迷宮 maze 中有一個(gè)球。球可以途經(jīng)空地向 上、下、左、右 四個(gè)方向滾動(dòng)，且在遇到墻壁前不會(huì)停止?jié)L動(dòng)。當(dāng)球停下時(shí)，可以選擇向下一個(gè)方向滾動(dòng)。
給你一個(gè)大小為 m x n 的迷宮 maze ，以及球的初始位置 start 和目的地 destination ，其中 start = [startrow, startcol] 且 destination = [destinationrow, destinationcol] 。請(qǐng)你判斷球能否在目的地停下：如果可以，返回 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
解釋：不存在能夠使球停在目的地的路徑。注意，球可以經(jīng)過目的地，但無(wú)法在那里停駐。
你可以 假定迷宮的邊緣都是墻壁（參考示例）。
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表示列
// 創(chuàng)建一個(gè)rowNum*colNum 的二維數(shù)組
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] { // 遇到終點(diǎn)返回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【會(huì)員/中等/BFS】
輸入 1: 迷宮由以下二維數(shù)組表示
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: 起始位置坐標(biāo) (rowStart, colStart) = (0, 4)
輸入 3: 目的地坐標(biāo) (rowDest, colDest) = (4, 4)
輸出: 12
// 有點(diǎn)難度了
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. 課程表【中等/拓?fù)渑判颉?/h3>
https://leetcode-cn.com/problems/course-schedule/solution/go-jian-dan-jie-fa-dfs-bfs-by-xilepeng-vhid/
210. 課程表 II【中等/拓?fù)渑判颉?/a>
2174. Remove All Ones With Row and Column Flips II（會(huì)員/中等/狀態(tài)壓縮/BFS/DFS）
317. 離建筑物最近的距離（會(huì)員/困難/BFS/做一下）
給你一個(gè) m × n 的網(wǎng)格，值為 0 、 1 或 2 ，其中:
每一個(gè) 0 代表一塊你可以自由通過的 空地
每一個(gè) 1 代表一個(gè)你不能通過的 建筑
每個(gè) 2 標(biāo)記一個(gè)你不能通過的 障礙
你想要在一塊空地上建造一所房子，在 最短的總旅行距離 內(nèi)到達(dá)所有的建筑。你只能上下左右移動(dòng)。
返回到該房子的 最短旅行距離 。如果根據(jù)上述規(guī)則無(wú)法建造這樣的房子，則返回 -1 。
總旅行距離 是朋友們家到聚會(huì)地點(diǎn)的距離之和。
使用 曼哈頓距離 計(jì)算距離，其中距離 (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
解析：給定三個(gè)建筑物 (0,0)、(0,4) 和 (2,2) 以及一個(gè)位于 (0,2) 的障礙物。
由于總距離之和 3+3+1=7 最優(yōu)，所以位置 (1,2) 是符合要求的最優(yōu)地點(diǎn)。
故返回7。
314. 二叉樹的垂直遍歷（會(huì)員/中等/BFS）
給你一個(gè)二叉樹的根結(jié)點(diǎn)，返回其結(jié)點(diǎn)按 垂直方向（從上到下，逐列）遍歷的結(jié)果。
如果兩個(gè)結(jié)點(diǎn)在同一行和列，那么順序則為 從左到右。
輸入：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. 墻與門（會(huì)員/中等/BFS）
你被給定一個(gè) m × n 的二維網(wǎng)格 rooms ，網(wǎng)格中有以下三種可能的初始化值：
-1 表示墻或是障礙物
0 表示一扇門
INF 無(wú)限表示一個(gè)空的房間。然后，我們用 231 - 1 = 2147483647 代表 INF。你可以認(rèn)為通往門的距離總是小于 2147483647 的。
你要給每個(gè)空房間位上填上該房間到 最近門的距離 ，如果無(wú)法到達(dá)門，則填 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. 二叉樹最近的葉節(jié)點(diǎn)（會(huì)員/中等/BFS/DFS）
給定一個(gè) 每個(gè)結(jié)點(diǎn)的值互不相同 的二叉樹，和一個(gè)目標(biāo)整數(shù)值 k，返回 樹中與目標(biāo)值 k 最近的葉結(jié)點(diǎn) 。
與葉結(jié)點(diǎn)最近 表示在二叉樹中到達(dá)該葉節(jié)點(diǎn)需要行進(jìn)的邊數(shù)與到達(dá)其它葉結(jié)點(diǎn)相比最少。而且，當(dāng)一個(gè)結(jié)點(diǎn)沒有孩子結(jié)點(diǎn)時(shí)稱其為葉結(jié)點(diǎn)。
輸入：root = [1, 3, 2], k = 1
輸出： 2
解釋： 2 和 3 都是距離目標(biāo) 1 最近的葉節(jié)點(diǎn)。
輸入：root = [1,2,3,4,null,null,null,5,null,6], k = 2
輸出：3
解釋：值為 3（而不是值為 6）的葉節(jié)點(diǎn)是距離結(jié)點(diǎn) 2 的最近結(jié)點(diǎn)。
1197. 進(jìn)擊的騎士（會(huì)員/中等/BFS/DFS）
一個(gè)坐標(biāo)可以從 -infinity 延伸到 +infinity 的 無(wú)限大的 棋盤上，你的 騎士 駐扎在坐標(biāo)為 [0, 0] 的方格里。
騎士的走法和中國(guó)象棋中的馬相似，走 “日” 字：即先向左（或右）走 1 格，再向上（或下）走 2 格；或先向左（或右）走 2 格，再向上（或下）走 1 格。
每次移動(dòng)，他都可以按圖示八個(gè)方向之一前進(jìn)。
返回 騎士前去征服坐標(biāo)為 [x, y] 的部落所需的最小移動(dòng)次數(shù) 。本題確保答案是一定存在的。
輸入：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. 不同島嶼的數(shù)量（會(huì)員/中等/BFS/DFS）
給定一個(gè)非空 01 二維數(shù)組表示的網(wǎng)格，一個(gè)島嶼由四連通（上、下、左、右四個(gè)方向）的 1 組成，你可以認(rèn)為網(wǎng)格的四周被海水包圍。
請(qǐng)你計(jì)算這個(gè)網(wǎng)格中共有多少個(gè)形狀不同的島嶼。兩個(gè)島嶼被認(rèn)為是相同的，當(dāng)且僅當(dāng)一個(gè)島嶼可以通過平移變換（不可以旋轉(zhuǎn)、翻轉(zhuǎn)）和另一個(gè)島嶼重合。
11000
11000
00011
00011
11011
10000
00001
11011
160. 相交鏈表（簡(jiǎn)單/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為根節(jié)點(diǎn)，則公共祖先為根節(jié)點(diǎn)
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分屬兩側(cè)，則公共祖先為根節(jié)點(diǎn)
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表和存儲(chǔ)走過的路利用hash表和存儲(chǔ)走過的路 ======
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/
/*思路：我們可以用哈希表存儲(chǔ)所有節(jié)點(diǎn)的父節(jié)點(diǎn)，然后我們就可以利用節(jié)點(diǎn)的父節(jié)點(diǎn)信息從 p 結(jié)點(diǎn)開始不斷往上跳，并記錄已經(jīng)訪問過的節(jié)點(diǎn)
，再?gòu)?q 節(jié)點(diǎn)開始不斷往上跳，如果碰到已經(jīng)訪問過的節(jié)點(diǎn)，那么這個(gè)節(jié)點(diǎn)就是我們要找的最近公共祖先。
算法：從根節(jié)點(diǎn)開始遍歷整棵二叉樹，用哈希表記錄每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)指針。從 p 節(jié)點(diǎn)開始不斷往它的祖先移動(dòng)，并用數(shù)據(jù)結(jié)構(gòu)記錄已經(jīng)訪問過的祖先節(jié)點(diǎn)。同樣，我們?cè)購(gòu)?q 節(jié)點(diǎn)開始不斷往它的祖先移動(dòng)，如果有祖先已經(jīng)被訪問過，即意味著這是 p 和 q 的深度最深的公共祖先，即 LCA節(jié)點(diǎn)。*/
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往上找父節(jié)點(diǎn)
}
return nil
}
1257. 最小公共區(qū)域（會(huì)員/中等/BFS/LCA）
給你一些區(qū)域列表 regions ，每個(gè)列表的第一個(gè)區(qū)域都包含這個(gè)列表內(nèi)所有其他區(qū)域。
很自然地，如果區(qū)域 X 包含區(qū)域 Y ，那么區(qū)域 X 比區(qū)域 Y 大。
給定兩個(gè)區(qū)域 region1 和 region2 ，找到同時(shí)包含這兩個(gè)區(qū)域的 最小 區(qū)域。
如果區(qū)域列表中 r1 包含 r2 和 r3 ，那么數(shù)據(jù)保證 r2 不會(huì)包含 r3 。
數(shù)據(jù)同樣保證最小公共區(qū)域一定存在。
輸入：
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），指的是在“樹”中尋找某兩個(gè)結(jié)點(diǎn)的最近的公共祖先。
https://leetcode.cn/problems/smallest-common-region/solution/javascript-shao-zheng-li-xia-lcawen-ti-de-si-lu-by/
思路：我們可以用哈希表存儲(chǔ)所有節(jié)點(diǎn)的父節(jié)點(diǎn)，然后我們就可以利用節(jié)點(diǎn)的父節(jié)點(diǎn)信息從 region1 結(jié)點(diǎn)開始不斷往上跳，并記錄已經(jīng)訪問過的節(jié)點(diǎn)，再?gòu)?region2 節(jié)點(diǎn)開始不斷往上跳，如果碰到已經(jīng)訪問過的節(jié)點(diǎn)，那么這個(gè)節(jié)點(diǎn)就是我們要找的最近公共祖先。
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 { // 很重要，這里必須要把根節(jié)點(diǎn)去了
continue
}
parent[regions[i][j]] = regions[i][0]
}
}
// fmt.Println(parent)
for region1 != "" { // 這里為啥是!=" 呢，因?yàn)樽钌系母?jié)點(diǎn)earth沒有父節(jié)點(diǎn)，他的父節(jié)點(diǎn)就是”“
visited[region1] = true
region1 = parent[region1]
}
for region2 != "" {
if visited[region2] {
return region2
}
region2 = parent[region2] // 從q往上找父節(jié)點(diǎn)
}
return ""
}
1273. 刪除樹節(jié)點(diǎn)（會(huì)員/中等/BFS/DFS）
給你一棵以節(jié)點(diǎn) 0 為根節(jié)點(diǎn)的樹，定義如下：
節(jié)點(diǎn)的總數(shù)為 nodes 個(gè)；
第 i 個(gè)節(jié)點(diǎn)的值為 value[i] ；
第 i 個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)是 parent[i] 。
請(qǐng)你刪除節(jié)點(diǎn)值之和為 0 的每一棵子樹。
在完成所有刪除之后，返回樹中剩余節(jié)點(diǎn)的數(shù)目。
輸入：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. 找到二叉樹中最近的右側(cè)節(jié)點(diǎn) （會(huì)員/中等/BFS/DFS）
1730. 獲取食物的最短路徑（會(huì)員/中等/BFS/DFS）(做一下)
你現(xiàn)在很餓，想要盡快找東西吃。你需要找到最短的路徑到達(dá)一個(gè)食物所在的格子。
給定一個(gè) m x n 的字符矩陣 grid ，包含下列不同類型的格子：
'*' 是你的位置。矩陣中有且只有一個(gè) '*' 格子。
'#' 是食物。矩陣中可能存在多個(gè)食物。
'O' 是空地，你可以穿過這些格子。
'X' 是障礙，你不可以穿過這些格子。
返回你到任意食物的最短路徑的長(zhǎng)度。如果不存在你到任意食物的路徑，返回 -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
解釋: 這里有多個(gè)食物。拿到下邊的食物僅需走 6 步。
1236. 網(wǎng)絡(luò)爬蟲（會(huì)員/中等/BFS/DFS）
237#
島嶼的最大面積
https://leetcode-cn.com/problems/course-schedule/solution/go-jian-dan-jie-fa-dfs-bfs-by-xilepeng-vhid/
給你一個(gè) m × n 的網(wǎng)格，值為 0 、 1 或 2 ，其中:
每一個(gè) 0 代表一塊你可以自由通過的 空地
每一個(gè) 1 代表一個(gè)你不能通過的 建筑
每個(gè) 2 標(biāo)記一個(gè)你不能通過的 障礙
你想要在一塊空地上建造一所房子，在 最短的總旅行距離 內(nèi)到達(dá)所有的建筑。你只能上下左右移動(dòng)。
返回到該房子的 最短旅行距離 。如果根據(jù)上述規(guī)則無(wú)法建造這樣的房子，則返回 -1 。
總旅行距離 是朋友們家到聚會(huì)地點(diǎn)的距離之和。
使用 曼哈頓距離 計(jì)算距離，其中距離 (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
解析：給定三個(gè)建筑物 (0,0)、(0,4) 和 (2,2) 以及一個(gè)位于 (0,2) 的障礙物。
由于總距離之和 3+3+1=7 最優(yōu)，所以位置 (1,2) 是符合要求的最優(yōu)地點(diǎn)。
故返回7。
給你一個(gè)二叉樹的根結(jié)點(diǎn)，返回其結(jié)點(diǎn)按 垂直方向（從上到下，逐列）遍歷的結(jié)果。
如果兩個(gè)結(jié)點(diǎn)在同一行和列，那么順序則為 從左到右。
輸入：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]]
你被給定一個(gè) m × n 的二維網(wǎng)格 rooms ，網(wǎng)格中有以下三種可能的初始化值：
-1 表示墻或是障礙物
0 表示一扇門
INF 無(wú)限表示一個(gè)空的房間。然后，我們用 231 - 1 = 2147483647 代表 INF。你可以認(rèn)為通往門的距離總是小于 2147483647 的。
你要給每個(gè)空房間位上填上該房間到 最近門的距離 ，如果無(wú)法到達(dá)門，則填 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]]
給定一個(gè) 每個(gè)結(jié)點(diǎn)的值互不相同 的二叉樹，和一個(gè)目標(biāo)整數(shù)值 k，返回 樹中與目標(biāo)值 k 最近的葉結(jié)點(diǎn) 。
與葉結(jié)點(diǎn)最近 表示在二叉樹中到達(dá)該葉節(jié)點(diǎn)需要行進(jìn)的邊數(shù)與到達(dá)其它葉結(jié)點(diǎn)相比最少。而且，當(dāng)一個(gè)結(jié)點(diǎn)沒有孩子結(jié)點(diǎn)時(shí)稱其為葉結(jié)點(diǎn)。
輸入：root = [1, 3, 2], k = 1
輸出： 2
解釋： 2 和 3 都是距離目標(biāo) 1 最近的葉節(jié)點(diǎn)。
輸入：root = [1,2,3,4,null,null,null,5,null,6], k = 2
輸出：3
解釋：值為 3（而不是值為 6）的葉節(jié)點(diǎn)是距離結(jié)點(diǎn) 2 的最近結(jié)點(diǎn)。
一個(gè)坐標(biāo)可以從 -infinity 延伸到 +infinity 的 無(wú)限大的 棋盤上，你的 騎士 駐扎在坐標(biāo)為 [0, 0] 的方格里。
騎士的走法和中國(guó)象棋中的馬相似，走 “日” 字：即先向左（或右）走 1 格，再向上（或下）走 2 格；或先向左（或右）走 2 格，再向上（或下）走 1 格。
每次移動(dòng)，他都可以按圖示八個(gè)方向之一前進(jìn)。
返回 騎士前去征服坐標(biāo)為 [x, y] 的部落所需的最小移動(dòng)次數(shù) 。本題確保答案是一定存在的。
輸入：x = 2, y = 1
輸出：1
解釋：[0, 0] → [2, 1]
輸入：x = 5, y = 5
輸出：4
解釋：[0, 0] → [2, 1] → [4, 2] → [3, 4] → [5, 5]
給定一個(gè)非空 01 二維數(shù)組表示的網(wǎng)格，一個(gè)島嶼由四連通（上、下、左、右四個(gè)方向）的 1 組成，你可以認(rèn)為網(wǎng)格的四周被海水包圍。
請(qǐng)你計(jì)算這個(gè)網(wǎng)格中共有多少個(gè)形狀不同的島嶼。兩個(gè)島嶼被認(rèn)為是相同的，當(dāng)且僅當(dāng)一個(gè)島嶼可以通過平移變換（不可以旋轉(zhuǎn)、翻轉(zhuǎn)）和另一個(gè)島嶼重合。
11000
11000
00011
00011
11011
10000
00001
11011
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為根節(jié)點(diǎn)，則公共祖先為根節(jié)點(diǎn)
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分屬兩側(cè)，則公共祖先為根節(jié)點(diǎn)
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表和存儲(chǔ)走過的路利用hash表和存儲(chǔ)走過的路 ======
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/
/*思路：我們可以用哈希表存儲(chǔ)所有節(jié)點(diǎn)的父節(jié)點(diǎn)，然后我們就可以利用節(jié)點(diǎn)的父節(jié)點(diǎn)信息從 p 結(jié)點(diǎn)開始不斷往上跳，并記錄已經(jīng)訪問過的節(jié)點(diǎn)
，再?gòu)?q 節(jié)點(diǎn)開始不斷往上跳，如果碰到已經(jīng)訪問過的節(jié)點(diǎn)，那么這個(gè)節(jié)點(diǎn)就是我們要找的最近公共祖先。
算法：從根節(jié)點(diǎn)開始遍歷整棵二叉樹，用哈希表記錄每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)指針。從 p 節(jié)點(diǎn)開始不斷往它的祖先移動(dòng)，并用數(shù)據(jù)結(jié)構(gòu)記錄已經(jīng)訪問過的祖先節(jié)點(diǎn)。同樣，我們?cè)購(gòu)?q 節(jié)點(diǎn)開始不斷往它的祖先移動(dòng)，如果有祖先已經(jīng)被訪問過，即意味著這是 p 和 q 的深度最深的公共祖先，即 LCA節(jié)點(diǎn)。*/
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往上找父節(jié)點(diǎn)
}
return nil
}
給你一些區(qū)域列表 regions ，每個(gè)列表的第一個(gè)區(qū)域都包含這個(gè)列表內(nèi)所有其他區(qū)域。
很自然地，如果區(qū)域 X 包含區(qū)域 Y ，那么區(qū)域 X 比區(qū)域 Y 大。
給定兩個(gè)區(qū)域 region1 和 region2 ，找到同時(shí)包含這兩個(gè)區(qū)域的 最小 區(qū)域。
如果區(qū)域列表中 r1 包含 r2 和 r3 ，那么數(shù)據(jù)保證 r2 不會(huì)包含 r3 。
數(shù)據(jù)同樣保證最小公共區(qū)域一定存在。
輸入：
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），指的是在“樹”中尋找某兩個(gè)結(jié)點(diǎn)的最近的公共祖先。
https://leetcode.cn/problems/smallest-common-region/solution/javascript-shao-zheng-li-xia-lcawen-ti-de-si-lu-by/
思路：我們可以用哈希表存儲(chǔ)所有節(jié)點(diǎn)的父節(jié)點(diǎn)，然后我們就可以利用節(jié)點(diǎn)的父節(jié)點(diǎn)信息從 region1 結(jié)點(diǎn)開始不斷往上跳，并記錄已經(jīng)訪問過的節(jié)點(diǎn)，再?gòu)?region2 節(jié)點(diǎn)開始不斷往上跳，如果碰到已經(jīng)訪問過的節(jié)點(diǎn)，那么這個(gè)節(jié)點(diǎn)就是我們要找的最近公共祖先。
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 { // 很重要，這里必須要把根節(jié)點(diǎn)去了
continue
}
parent[regions[i][j]] = regions[i][0]
}
}
// fmt.Println(parent)
for region1 != "" { // 這里為啥是!=" 呢，因?yàn)樽钌系母?jié)點(diǎn)earth沒有父節(jié)點(diǎn)，他的父節(jié)點(diǎn)就是”“
visited[region1] = true
region1 = parent[region1]
}
for region2 != "" {
if visited[region2] {
return region2
}
region2 = parent[region2] // 從q往上找父節(jié)點(diǎn)
}
return ""
}
給你一棵以節(jié)點(diǎn) 0 為根節(jié)點(diǎn)的樹，定義如下：
節(jié)點(diǎn)的總數(shù)為 nodes 個(gè)；
第 i 個(gè)節(jié)點(diǎn)的值為 value[i] ；
第 i 個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)是 parent[i] 。
請(qǐng)你刪除節(jié)點(diǎn)值之和為 0 的每一棵子樹。
在完成所有刪除之后，返回樹中剩余節(jié)點(diǎn)的數(shù)目。
輸入：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
你現(xiàn)在很餓，想要盡快找東西吃。你需要找到最短的路徑到達(dá)一個(gè)食物所在的格子。
給定一個(gè) m x n 的字符矩陣 grid ，包含下列不同類型的格子：
'*' 是你的位置。矩陣中有且只有一個(gè) '*' 格子。
'#' 是食物。矩陣中可能存在多個(gè)食物。
'O' 是空地，你可以穿過這些格子。
'X' 是障礙，你不可以穿過這些格子。
返回你到任意食物的最短路徑的長(zhǎng)度。如果不存在你到任意食物的路徑，返回 -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
解釋: 這里有多個(gè)食物。拿到下邊的食物僅需走 6 步。
