首页 > itarticle > l637 average of levels in binary tree

l637 average of levels in binary tree

admin 11月 13, 2020 0

题目描述

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.

解题思路

使用BFS，利用队列循环实现

Go实现

Go实现——BFS，队列循环实现


func (root *TreeNode) []float64 {
    if root == nil{
        return []float64{}
    }
    path := []float64{}
    queue := []*TreeNode{}
    queue = append(queue, root)

    for len(queue)>0 {

        n := len(queue)
        var s float64
        for i:=0;i<n ; i++ {
            current := queue[0]
            queue = queue[1:]
            s+= float64(current.Val)
            if current.Left != nil {
                queue = append(queue, current.Left)
            }

            if current.Right != nil {
                queue = append(queue, current.Right)
            }
        }
        path = append(path, s/float64(n))
    }
    return path
}

Runtime: 44 ms 30.56%