BFS
LC 111. Minimum Depth of Binary Tree 二叉树的最小深度
https://leetcode.com/problems/minimum-depth-of-binary-tree/
DFS 解法
/**
* 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
}
return dfs(root)
}
func dfs(root *TreeNode) int {
if root.Left == nil && root.Right == nil {
return 1
}
if root.Left == nil {
return dfs(root.Right) + 1
}
if root.Right == nil {
return dfs(root.Left) + 1
}
return min(dfs(root.Left), dfs(root.Right)) + 1
}
BFS 解法
/**
* 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
}
q := make([]*TreeNode, 0, 10_0000)
q = append(q, root)
depth := 1
for len(q) > 0 {
sz := len(q)
for i := 0; i < sz; i++ {
node := q[i]
if node.Left == nil && node.Right == nil {
return depth
}
if node.Left != nil {
q = append(q, node.Left)
}
if node.Right != nil {
q = append(q, node.Right)
}
}
depth++
q = q[sz:]
}
panic("impossible")
}
BFS 进一步优化空间占用
在 Go 中，如果采用 q = q[x:] 这种写法，会导致前 x 个的内存无法释放
/**
* 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
}
var q []*TreeNode
q = append(q, root)
depth := 1
for len(q) > 0 {
sz := len(q)
qq := q
q = nil
for i := 0; i < sz; i++ {
node := qq[i]
if node.Left == nil && node.Right == nil {
return depth
}
if node.Left != nil {
q = append(q, node.Left)
}
if node.Right != nil {
q = append(q, node.Right)
}
}
depth++
}
panic("impossible")
}
LC 752. Open the Lock 打开转盘锁
https://leetcode.com/problems/open-the-lock/
func openLock(deadends []string, target string) int {
var q []string
visited := make(map[string]bool)
for _, x := range deadends {
visited[x] = true
}
if visited["0000"] {
return -1
}
q = append(q, "0000")
visited["0000"] = true
step := 0
for len(q) > 0 {
qq := q
q = nil
for _, node := range qq {
if node == target {
return step
}
for _, next := range getNext(node) {
if visited[next] {
continue
}
q = append(q, next)
visited[next] = true
}
}
step++
}
return -1
}
func getNext(node string) []string {
result := make([]string, 0, 8)
nb := []byte(node)
add := func(i, x int) {
v := (int(nb[i] - '0') + x + 10) % 10
nb[i] = '0' + byte(v)
}
for i := 0; i < 4; i++ {
add(i, 1)
result = append(result, string(nb))
add(i, -2)
result = append(result, string(nb))
add(i, 1)
}
return result
}
优化：双向 BFS
头尾同时遍历（实际代码上是遍历一端完再遍历另一端），出现交集时返回
func openLock(deadends []string, target string) int {
visited := make(map[string]bool)
for _, x := range deadends {
visited[x] = true
}
if visited["0000"] {
return -1
}
q1 := make(map[string]bool)
q2 := make(map[string]bool)
q1["0000"] = true
q2[target] = true
step := 0
for len(q1) > 0 && len(q2) > 0 {
temp := make(map[string]bool)
for node := range q1 {
if q2[node] {
return step
}
visited[node] = true
for _, next := range getNext(node) {
if visited[next] {
continue
}
temp[next] = true
}
}
step++
q1, q2 = q2, temp
}
return -1
}
func getNext(node string) []string {
result := make([]string, 0, 8)
nb := []byte(node)
add := func(i, x int) {
v := (int(nb[i] - '0') + x + 10) % 10
nb[i] = '0' + byte(v)
}
for i := 0; i < 4; i++ {
add(i, 1)
result = append(result, string(nb))
add(i, -2)
result = append(result, string(nb))
add(i, 1)
}
return result
}