力扣 111. 二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
方案一：递归，遍历每一个节点。（自底向上统计信息，分治思想）
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func minDepth(root *TreeNode) int {
// 如果当前节点为空则直接返回 0
if root == nil {
return 0
}
// 如果当前节点是叶子结点，则直接返回当前的层高 1
if root.Left == nil && root.Right == nil {
return 1
}
// 左右子树中有至少一个不为空，则比较计算左右子树中的最小深度
minD := math.MaxInt32
if root.Left != nil {
minD = min(minD, minDepth(root.Left))
}
if root.Right != nil {
minD = min(minD, minDepth(root.Right))
}
// + 1 是为了记录当前的层高
return minD + 1
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
- 时间复杂度：O(n)，n 为树中节点个数，因为需要遍历树中每个节点，所以时间复杂度为 O(n)。
- 空间复杂度：O(n)，n 为树中节点个数，树在最好情况下深度为 logn，最差情况下为 n，所以空间复杂度为 O(n)。
方案二：递归，遍历每一个节点。（自顶向下维护信息，在叶子处计算结果）
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
var ans int
func minDepth(root *TreeNode) int {
if root == nil {
return 0
}
// 定义一个极大值（类似于哨兵值）
ans = math.MaxInt32
// 开始递归
recur(root, 0)
return ans
}
func recur(root *TreeNode, dept int) {
// 层数 + 1
dept++
// 如果是叶子结点，则计算结果
if root.Left == nil && root.Right == nil {
ans = min(ans, dept)
return
}
// 非叶子结点，必定存在子树
// 递归子树
if root.Left != nil {
recur(root.Left, dept)
}
if root.Right != nil {
recur(root.Right, dept)
}
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
- 时间复杂度：O(n)，n 为树中节点个数，因为需要遍历树中每个节点，所以时间复杂度为 O(n)。
- 空间复杂度：O(n)，n 为树中节点个数，树在最好情况下深度为 logn，最差情况下为 n，所以空间复杂度为 O(n)。