```
# 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]
"""
def bfs(root,result):
if root:
q = []
q.append(root)
q.append(None)
xsum = 0
n = 0
while q:
x = q.pop(0)
if x is None:
# new level found!
result.append( xsum / float(n ) )
xsum = 0
n = 0
if q:
q.append(None)
else:
xsum += x.val
n += 1
if x.left:
q.append(x.left)
if x.right:
q.append(x.right)
return result
return bfs(root,[])
```