题目：Average of Levels in Binary Tree
Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array
Example:
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].
BFS解：
解法在计算均值处太埋汰，可以选择性无视
# -*- coding:utf-8 -*-
# 2017/7/17
# 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):
@staticmethod
def average_of_levels(root):
"""
:param root: Tree Node
:return: List[float]
"""
S, Q = list(), list()
Q.append((0, root))
while Q:
level, u = Q[0] #1
Q = Q[1:] #2
S.append((level, u.val))
if u.left:
Q.append((level+1, u.left))
if u.right:
Q.append((level+1, u.right))
# print level, u.val
# print S
from collections import defaultdict
result = defaultdict(list)
for each in S:
level, val = each[0], each[1]
result[level].append(val)
# print result
re = [0 for i in range(max(result.keys())+1)]
for i, j in enumerate(re):
re[i] = float(sum(result[i]))/len(result[i])
return re
root = TreeNode(3)
root.left = TreeNode(9)
root.left.left = TreeNode(3)
root.left.right = TreeNode(6)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
Solution.average_of_levels(root)
后记：
1.这个题目中的坑主要是在二叉树中每一层中的节点个数不定，很容易忽视。
2.虽然题目的难度不大，但是这个题目对于个人而言还是有不少收获的，主要就是在算法设计问题上的一次理论应用吧，因为面对一个问题的时候，我往往都是埋头去暴力猜解，而忽略了在解决问题中最主要的一步“前期思路分析”。
3.问题不难，简单一看完全可以运用算法设计中的归简法处理，因为此题目解决问题主要就是两个步骤，“图的遍历”和“均值计算”。把一个复杂问题拆解为多个简单的问题，之后再做合并，之后得出结论，这就是归简法的一种应用吧，正规军的套路往往更注重的是培养解决问题的能力，而不是解决问题！
4.虽然代码里的计算均值的过程很埋汰，但是呢，图的遍历还是有个地方值得说的，那就是Q这个队列。
想想如果我把1，2两行中的：
u=Q[0];
Q=Q[1:]
#换成
u=Q.pop()
会怎样？
