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.
这道题描述的是：
给我们一颗完全二叉树，我们求出二叉树每层的节点平均值
我的思想：
对二叉树进行广度遍历，用一个二维数组存下每一层的所有节点
再对每一层所有节点进行求平均数
伪代码：
python中数组是动态的
用一个levels列表，里面每一个元素都是一个列表，列表里存着每层的所有节点
广度遍历的时候，动态生成下一个元素和下一层列表
1 levels = [[root] ] 根自己是第一层，levels里面
2 对levels 一个一个拿出里面的列表用level表示
（如果取出来的是空列表，说明到最后一层了，跳出循环）
2.1 当前列表level为一层，里面存着所有当前层元素
2.2 为levels追加一个空列表[] 用于存储下一层
2.3 一个一个取出level里面的元素node
如果 node有left，node.left追加到下一层列表
如果 node有right，node.right追加到下一层列表
2.4 计算当前层所有节点的平均值，追加大结果列表res
我的python代码：
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def averageOfLevels(self, root):
"""
:type root: TreeNode
:rtype: List[float]
"""
levels = [[root]] #将要进行广度遍历，每一层新开一个列表，每个列表存着每层的节点
res = [ ] #用于存储每层的平均数
i = 0
while i < len(levels) and levels[i] != []:
level = levels[i]
j = 0
temp = 0 # 临时变量用于存储当前层的节点值加和
levels.append([]) #开启新的一层
while j < len(level):
node = level[j]
if node.left is not None:
levels[i+1].append(node.left)
if node.right is not None:
levels[i+1].append(node.right)
temp+=node.val
j += 1
res.append(temp/j)
i += 1
return res
