# 给定一个非空二叉树, 返回一个由每层节点平均值组成的数组.
#
# 示例 1:
#
# 输入:
#     3
#    / \
#   9  20
#     /  \
#    15   7
# 输出: [3, 14.5, 11]
# 解释:
# 第0层的平均值是 3,  第1层是 14.5, 第2层是 11. 因此返回 [3, 14.5, 11].
# 注意：
#
# 节点值的范围在32位有符号整数范围内。
#
# 来源：力扣（LeetCode）
# 链接：https://leetcode-cn.com/problems/average-of-levels-in-binary-tree
# 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
from typing import List
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def averageOfLevels(self, root: TreeNode) -> List[float]:
        if not root:
            return []
        workq = [[root]]
        ans = []
        while workq:
            nodes = workq.pop(0)
            inner = []
            innerq = []
            for n in nodes:
                if n.left: innerq.append(n.left)
                if n.right: innerq.append(n.right)
                inner.append(n.val)
            if innerq: workq.append(innerq)
            if inner: ans.append(inner)
        return list(map(lambda xs: sum(xs) / len(xs), ans))