BFS
LC 111. Minimum Depth of Binary Tree 二叉树的最小深度
https://leetcode.com/problems/minimum-depth-of-binary-tree/
...
| Code Block |
|---|
|
/**
* 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 解法
| Code Block |
|---|
|
/**
* 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 个的内存无法释放
| Code Block |
|---|
/**
* 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/
| Code Block |
|---|
|
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
头尾同时遍历（实际代码上是遍历一端完再遍历另一端），出现交集时返回
| Code Block |
|---|
|
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
} |
二叉树
...
LC 144. Binary Tree Preorder Traversal 二叉树的前序遍历
https://leetcode.com/problems/binary-tree-preorder-traversal/description/
| Code Block |
|---|
|
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func preorderTraversal(root *TreeNode) (result []int) {
var traverse func(node *TreeNode)
traverse = func(node *TreeNode) {
if node == nil {
return
}
result = append(result, node.Val)
traverse(node.Left)
traverse(node.Right)
}
traverse(root)
return
} |
LC 543. Diameter of Binary Tree 二叉树的直径
https://leetcode.com/problems/diameter-of-binary-tree/description/
二叉树的直径定义：二叉树中任意两个节点的最大距离（边数）
| Code Block |
|---|
|
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func diameterOfBinaryTree(root *TreeNode) (diameter int) {
traverse(root, &diameter)
return
}
func traverse(root *TreeNode, diameter *int) int {
if root == nil {
return 0
}
leftCount := traverse(root.Left, diameter)
rightCount := traverse(root.Right, diameter)
*diameter = max(*diameter, leftCount + rightCount + 1)
return max(leftCount, rightCount) + 1
} |
LC 104. Maximum Depth of Binary Tree 二叉树的最大深度
https://leetcode.com/problems/maximum-depth-of-binary-tree/description/
深度：从根节点到叶子结点的最长节点数
| Code Block |
|---|
|
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}
return max(maxDepth(root.Left), maxDepth(root.Right)) + 1
} |