637 二叉树的层平均值

题目描述#

给定一个非空二叉树的根节点 root，以数组的形式返回每一层节点的平均值。

思路#

用 BFS 层序遍历，每次处理完整的一层。记录当前层的节点数 queueSize，遍历该层时累加所有节点值到 sum，最后将 sum / queueSize 追加到结果中。

每处理一个节点，把它的左、右子节点依次加入队列，保证下一层的节点按顺序入队。整体和层序遍历的模板基本一致，只是把"取最后一个"换成了"求平均"。

代码#

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func averageOfLevels(root *TreeNode) []float64 {
    // 用一个queue队列保存层序遍历的结果
    queue := []*TreeNode{root}
    ans := []float64{}
    for len(queue) != 0 {
        queueSize := len(queue)
        sum := 0.0
        for i := 0; i < queueSize; 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)
            }

        }
        ans = append(ans, sum/float64(queueSize))
    }
    return ans
}