目录

一、题目内容

二、解题思路

三、代码

一、题目内容

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。

示例 1：

输入：
    3
   / \
  9  20
    /  \
   15   7
输出：[3, 14.5, 11]
解释：
第 0 层的平均值是 3 ,  第1层是 14.5 , 第2层是 11 。因此返回 [3, 14.5, 11] 。

提示：

节点值的范围在32位有符号整数范围内。

二、解题思路

记录每个深度的节点个数，每加一个数都求平均。

从添加的第三个数开始，平均值=原始的和* (已经加和节点个数 / (已经加和节点个数 + 1)) + 当前节点值 / (已经加和节点个数 + 1) 

三、代码

# Definition for a binary tree node.
class TreeNode:def __init__(self, x):self.val = xself.left = Noneself.right = Nonedef __repr__(self):return str(self.val)class Solution:def averageOfLevels(self, root: TreeNode) -> list:self.len_res = []self.res = []def dfs(root, depth):if not root:return 0if depth == len(self.res):self.res.append(float(root.val))self.len_res.append(1)else:if self.len_res[depth] == 1:self.res[depth] = float((self.res[depth] + root.val) / (self.len_res[depth] + 1))self.len_res[depth] += 1elif self.len_res[depth] > 1:self.res[depth] = float(self.res[depth] * self.len_res[depth] / (self.len_res[depth] + 1) + 1. * root.val / (self.len_res[depth] + 1))self.len_res[depth] += 1dfs(root.left, depth + 1)dfs(root.right, depth + 1)dfs(root, 0)return self.resif __name__ == '__main__':# a = TreeNode(3)# a.left = TreeNode(9)# a.right = TreeNode(20)# # a.right.left = TreeNode(15)# # a.right.right = TreeNode(7)# a.left.left = TreeNode(15)# a.left.right = TreeNode(7)a = TreeNode(3)a.left = TreeNode(1)a.right = TreeNode(5)a.left.left = TreeNode(0)a.left.right = TreeNode(2)a.right.left = TreeNode(4)a.right.right = TreeNode(6)s = Solution()ans = s.averageOfLevels(a)print(ans)