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")
}