难度: Easy
给定一个非空二叉树的根节点 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] 范围内-231 <= Node.val <= 231 - 1运行时间: 23 ms
内存: 18.2 MB
# 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]:
if not root: return []
res = []
treeQueue = collections.deque([root])
while treeQueue:
levelsum = 0
levellen = len(treeQueue)
for _ in range(levellen):
node = treeQueue.popleft()
if node.left: treeQueue.append(node.left)
if node.right: treeQueue.append(node.right)
levelsum += node.val
res.append(levelsum / levellen)
return res
这个题解使用了BFS（广度优先搜索）的思路。具体来说，使用一个队列 treeQueue 来存储每一层的节点。首先将根节点入队，然后进入循环：将当前队列中的所有节点逐个出队，计算它们的值的总和，并将它们的非空子节点入队。这样就可以确保每次循环处理一层节点。将当前层节点值的总和除以节点数，就得到了这一层的平均值，将其存入结果数组中。当队列为空时，说明所有节点都已访问过，循环结束，返回结果数组。
时间复杂度: O(n)
空间复杂度: O(n)
# 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]:
if not root: return []
res = []
treeQueue = collections.deque([root]) # 初始时将根节点入队
while treeQueue:
levelsum = 0
levellen = len(treeQueue) # 当前层的节点数
for _ in range(levellen):
node = treeQueue.popleft() # 将当前层的节点逐个出队
if node.left: treeQueue.append(node.left) # 将下一层非空节点入队
if node.right: treeQueue.append(node.right)
levelsum += node.val # 累加当前层的节点值
res.append(levelsum / levellen) # 计算当前层的平均值并添加到结果中
return res
在Python中，使用deque作为队列的主要优势在于其高效的队首操作。对于deque，无论是append还是popleft操作，时间复杂度都是O(1)。而使用list时，虽然末尾的append操作时间复杂度是O(1)，但是pop操作（从列表开始位置移除元素）的时间复杂度是O(n)，因为它需要移动所有其它元素来填补被移除元素留下的空位。在BFS中，我们需要频繁地添加和移除队列的元素，因此使用deque可以显著提高效率。
是的，在计算层的总和时，如果节点值非常大，确实存在整数溢出的风险。Python的整数类型在内部使用长整型（长整数），这意味着它们可以处理非常大的数，但理论上仍有溢出的可能性，尤其是在其他编程语言中。为了避免溢出，可以在计算过程中采用逐步求平均的策略，即每个节点值除以节点总数，然后累加这些部分平均值来得到最终的平均数。这样可以减少单次加法操作的数值范围，从而降低溢出风险。
在计算平均值时，节点的值是否为负数不会影响求平均的过程本身。无论正数还是负数，平均值的计算方法都是相同的，即求总和后除以数量。然而，如果存在负数，它会直接影响总和的结果，从而影响平均值的大小。因此，算法能够正确处理负数值，只要确保所有节点的值被正确加总即可。
在计算机中，浮点数的运算通常涉及一定的舍入误差，因为浮点数的表示是有限的，不可能精确表示所有实数。为了确保精度在`10^-5`以内，通常会通过足够的浮点数精度（例如使用double类型而不是float）来减少误差。Python的float采用双精度浮点数表示，这足以保证普通应用中的计算精度。在提交解答时，可以通过比较预期结果与实际结果的差值是否小于`10^-5`来检验精度是否符合要求。