目录

一、题目内容

二、解题思路

三、代码

一、题目内容

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

示例 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 = x
     
    
   

    

     

    
    

     

       self.left = None
     
    
   

    

     

    
    

     

       self.right = None
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 def __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 0
     
    
   

    

     

    
    

     
 if 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] += 1
     
    
   

    

     

    
    

     
 elif 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] += 1
     
    
   

    

     

    
    

     

       dfs(root.left, depth + 1)
     
    
   

    

     

    
    

     

       dfs(root.right, depth + 1)
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       dfs(root, 0)
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 return self.res
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      if __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)
     
    
  
 

文章来源: nickhuang1996.blog.csdn.net，作者：悲恋花丶无心之人，版权归原作者所有，如需转载，请联系作者。

原文链接：nickhuang1996.blog.csdn.net/article/details/108738261