【题目描述】
给定一个非空二叉树, 返回一个由每层节点平均值组成的数组.
【示例】
输入:
3
/ \
9 20
/ \
15 7
输出: [3, 14.5, 11]
解释:
第0层的平均值是 3, 第1层是 14.5, 第2层是 11. 因此返回 [3, 14.5, 11].
节点值的范围在32位有符号整数范围内。
【思路1】
1、使用队列
2、判断队列是否为空，为空循环终止
3、内层循环的次数是当前队列元素的个数
4、时间复杂度O(m*n) m为层数 n为每层的结点个数
5、空间复杂度O(n)
代码实现：
func averageOfLevels(_ root: TreeNode?) -> [Double] {
var res = [Double]()
var queue = Queue<TreeNode?>.init()
queue.push(x: root)
while !queue.isEmpty() {
var sum = 0.0
var count = queue.size()
let num = count
while count > 0 {
let node = queue.pop()
sum+=Double((node?.val ?? 0))
count-=1
if node?.left != nil {
queue.push(x: node?.left)
}
if node?.right != nil {
queue.push(x: node?.right)
}
}
res.append(sum/Double(num))
}
return res
}
【思路2】
1、不适用队列 迭代实现
2、时间复杂度O(m*n) m为层数 n为每层的结点个数
3、空间复杂度O(n)
代码实现：
func averageOfLevels(_ root: TreeNode?) -> [Double] {
var res = [Double]()
var nodes = [root]
while nodes.count > 0 {
var tmp = [TreeNode]()
var sum = 0.0
let count = nodes.count
for n in nodes {
sum+=Double(n?.val ?? 0)
if let left = n?.left {
tmp.append(left)
}
if let right = n?.right {
tmp.append(right)
}
}
nodes = tmp
res.append(sum/Double(count))
}
return res
}
