43 lines
826 B
Go
43 lines
826 B
Go
package q637
|
|
|
|
type TreeNode struct {
|
|
Val int
|
|
Left *TreeNode
|
|
Right *TreeNode
|
|
}
|
|
|
|
func averageOfLevels(root *TreeNode) []float64 {
|
|
type qElem struct {
|
|
level int
|
|
node *TreeNode
|
|
}
|
|
|
|
ret := []float64{}
|
|
level := 0
|
|
n := 0 // number of nodes
|
|
var sum float64
|
|
|
|
queue := []qElem{{level: 0, node: root}}
|
|
for ; len(queue) > 0; queue = queue[1:] {
|
|
curr := &queue[0]
|
|
if curr.level == level {
|
|
sum += float64(curr.node.Val)
|
|
n++
|
|
} else {
|
|
ret = append(ret, sum/float64(n))
|
|
sum = float64(curr.node.Val)
|
|
n = 1
|
|
level = curr.level
|
|
}
|
|
if curr.node.Left != nil {
|
|
queue = append(queue, qElem{curr.level + 1, curr.node.Left})
|
|
}
|
|
if curr.node.Right != nil {
|
|
queue = append(queue, qElem{curr.level + 1, curr.node.Right})
|
|
}
|
|
}
|
|
ret = append(ret, sum/float64(n))
|
|
return ret
|
|
}
|
|
|
|
var _ = averageOfLevels
|