❝

这是一道 「简单」 题
https://leetcode.cn/problems/minimum-depth-of-binary-tree/

❞

题目

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

示例 1：

/**
 * 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
    }

    queue := []*TreeNode{root}
    depth := 1

    for len(queue) > 0 {
        // 同一层节点个数
        len := len(queue)
        
        // 将同一层节点全部取出，并将下一层节点入队
        for i := 0; i < len; 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
}

复杂度分析

• 「时间复杂度」：，N 为二叉树中节点的个数，最坏的情况下需要遍历每一个节点。
• 「空间复杂度」：，N 为二叉树中节点的个数，空间复杂度主要取决于队列的大小，最差的情况就是放 N 个元素。

总结

「简单递归解法」 的思路最为简单，但是需要计算所有节点，所以效率上不是最好的。

「DFS」 和 「BFS」 虽然时间复杂度上也都是，但这是在最坏的情况下得到的，通常都不需要遍历所有节点，所以效率要高一些。

因为 「BFS」 比 「DFS」 所需要遍历的节点数会更少一些，所以个人觉得求最小深度（最短路径）的题目时使用 「BFS」 更为合适一些。