# 637. 二叉树的层平均值

#也不是一层一层输出，每层只有一个平均值

# 求层平均值，需要记录下每层结点的数目

#另外除法需要注意取整的问题

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
# 20220114 复习
from collections import deque
class Solution(object):
    def averageOfLevels(self, root):
        """
        :type root: TreeNode
        :rtype: List[float]
        """
        # 不是一层一层输出
        # 求层平均值，需要记录下每层结点的数目，另外除法需要注意取整的问题
        if not root:
            return []
        que = deque([root])
        result = []
        while que:
            sum_ = 0
            node_sum = len(que)
            for _ in range(node_sum):
                cur = que.popleft()
                sum_ += cur.val
                if cur.left:
                    que.append(cur.left)
                if cur.right:
                    que.append(cur.right)
            result.append(sum_/float(node_sum))
        return result