637. Average of Levels in Binary Tree

Leetcode 链接

题目

Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.

Example 1:
Input:
    3
   / \
  9  20
    /  \
   15   7
Output: [3, 14.5, 11]

Explanation: The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11]. Note: The range of node's value is in the range of 32-bit signed integer.

题意解析

求二叉树每一层的平均数

解决方案

• 对二叉树进行层序遍历
• 这个题目有点坑，如果使用全局变量，那么测试提交和正式提交出来的结果不同，可能是 leetcode 后台环境问题。最终代码里没有用全局变量。

Go 代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

type record struct {
    val float64
    num int
}

func averageOfLevels(root *TreeNode) []float64 {
    res := make([]record, 0)
    helper(root, &res, 1)

    r := make([]float64, 0)
    for _, v := range res {
        r = append(r, v.val/float64(v.num))
    }

    return r
}

func helper(root *TreeNode, res *[]record, level int) {
    if root == nil {
        return
    }

    if len(*res) < level {
        *res = append(*res, record{})
    }

    (*res)[level-1].val += float64(root.Val)
    (*res)[level-1].num += 1

    helper(root.Left, res, level+1)
    helper(root.Right, res, level+1)
}