[数据结构与算法]LeetCode简单题之二叉树的层平均值

题目

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。
示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[3.00000,14.50000,11.00000]
解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。
因此返回 [3, 14.5, 11] 。
示例 2:

输入：root = [3,9,20,15,7]
输出：[3.00000,14.50000,11.00000]
提示：
树中节点数量在 [1, 104] 范围内
-2^31 <= Node.val <= 2 ^31 - 1

来源：力扣（LeetCode）

解题思路

??一个非常直观的思路就是层序遍历的变种。修改层序遍历让队列每次都清空之后再进行入队操作，这也可以有效的计算一层有多少结点以及每层的总和。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        Q=deque()
        Q.append(root)
        ans=[]
        temp=[]
        while Q:
            q=Q.popleft()
            temp.append(q)
            if len(Q)==0:
                ans.append(sum([j.val for j in temp])/len(temp))
                for i in temp:
                    if i.left:
                        Q.append(i.left)
                    if i.right:
                        Q.append(i.right)
                temp.clear()
        return ans