LeetCode 637. 二叉树的层平均值

题目描述

✅ 637. 二叉树的层平均值

image-20250510081805872

image-20250510081826077

思路分析

层序遍历

参考代码



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



func averageOfLevels(root *TreeNode) []float64 {
    if root == nil {
        return nil
    }

    var res []float64
    queue := []*TreeNode{root}

    for len(queue) > 0 {
        size := len(queue)
        sum := 0.0 // 每层的总和

        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            sum += float64(node.Val)

            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }

        res = append(res, sum/float64(size)) // 计算平均值
    }

    return res
}
  • 时间复杂度：O(n)，每个节点只遍历一次。
  • 空间复杂度：O(m)，其中 m 为某一层最多的节点数，即队列最大长度。

➡️ 点击查看 Java 题解



1



write your code here
本文作者:
本文链接: https://hgnulb.github.io/blog/2021/67992061
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！