一、问题描述

给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。说明: 叶子节点是指没有子节点的节点。

示例:

给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回它的最小深度 2.

二、方案一：深度优先搜索（DFS）

1、思路

深度优先搜索（DFS）是二叉树问题的常用方法。我们可以从根节点开始，递归地遍历每个节点，同时记录从根节点到当前节点的路径长度。当遇到叶子节点时，我们更新最小深度。

2、代码实现

func minDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    if root.Left == nil && root.Right == nil {
        return 1
    }
    minD := math.MaxInt32
    if root.Left != nil {
        minD = min(minDepth(root.Left), minD)
    }
    if root.Right != nil {
        minD = min(minDepth(root.Right), minD)
    }
    return minD + 1
}
func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

3、复杂度分析

• 时间复杂度：O(N)，其中 N 是树的节点数。在最坏的情况下，树是完全二叉树，我们需要遍历所有节点。
• 空间复杂度：O(H)，其中 H 是树的高度。在最坏的情况下，树是完全不平衡的，例如每个节点都只有左子节点，递归会调用 O(H) 次，因此栈的空间复杂度是 O(H)。

三、方案二：广度优先搜索（BFS）

1、思路

广度优先搜索（BFS）可以保证我们找到的第一个叶子节点就是最小深度的节点。我们从根节点开始，逐层遍历树，每遍历一层，深度加一。当我们遇到叶子节点时，返回当前的深度。

2、代码实现

func minDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    queue := []*TreeNode{root}
    depth := 1
    for len(queue) > 0 {
        size := len(queue)
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            if node.Left == nil && node.Right == nil {
                return depth
            }
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        depth++
    }
    return depth
}

3、复杂度分析

• 时间复杂度：O(N)，其中 N 是树的节点数。在最坏的情况下，树是完全二叉树，我们需要遍历所有节点。
• 空间复杂度：O(N)，其中 N 是树的节点数。在最坏的情况下，树是完全不平衡的，例如每个节点都只有左子节点，我们需要存储所有的 N 个节点。

四、总结

方案	时间复杂度	空间复杂度	备注
方案一	O(N)	O(H)	适用于一般情况
方案二	O(N)	O(N)	适用于查找最小深度

两种方案都可以解决问题，但 BFS 更适合于查找最小深度，因为它可以保证我们找到的第一个叶子节点就是最小深度的节点。