637. 二叉树的层平均值

题目-简单难度

给定一个非空二叉树的根节点 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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/summary-ranges
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1. bfs

时间
40ms
击败 60.54%使用 Python 的用户
内存
17.18MB
击败 26.91%使用 Python 的用户

# 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
class Solution(object):
    def averageOfLevels(self, root):
        """
        :type root: TreeNode
        :rtype: List[float]
        """
        # 根节点为第一行
        li = [root]
        res = []
        # 遍历每一行
        while li:
            avg = 0
            count = 0
            # 遍历当前行的所有节点
            for _ in range(len(li)):
                # 获取节点
                a = li.pop(0)
                # 如果节点存在, 将节点累加并且统计节点数量
                # 同时判断是否存在左右子节点,若存在,将节点添加到列表, 作为下一行遍历
                if a:
                    avg+=a.val
                    count+=1
                    if a.left:
                        li.append(a.left)
                    if a.right:
                        li.append(a.right)
            # 统计需要把avg转换为float, 这样才能有小数点计算
            res.append(float(avg)/count)
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36