返回

LeetCode 0111.二叉树的最小深度

二叉树的最小深度

LeetCode111. 二叉树的最小深度

题目描述

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

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

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

思路

本题使用层序遍历的方式来解决,只有当左右孩子都为空的时候,才说明找到了最小深度。如果其中一个孩子为空则不是最小深度。

代码

Go

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func minDepth(root *TreeNode) int {
    if root == nil {
        // 根节点为空
        return 0
    }
    // 用切片模拟队列
    queue := make([]*TreeNode, 0)
    // 根节点入队
    queue = append(queue, root)
    // 最小深度初始化为1
    minDepth := 1
    // 遍历二叉树
    for len(queue) > 0 {
        // 记录当前层节点数
        l := len(queue)
        // 遍历一层
        for i := 0; i < l; i++ {
            // 当前节点没有子节点,返回当前深度
            if queue[0].Left == nil && queue[0].Right == nil {
                return minDepth
            }
            // 若当前节点有子节点,则入队
            if queue[0].Left != nil {
                // 左子节点入队
                queue = append(queue, queue[0].Left)
            }
            if queue[0].Right != nil {
                // 右子节点入队
                queue = append(queue, queue[0].Right)
            }
            // 当前节点出队
            queue = queue[1:]
        }
        // 该层节点都有子节点,最小深度+1
        minDepth++
    }
    return minDepth
}

GitHub

Built with Hugo
Theme Stack designed by Jimmy