1120. 子树的最大平均值

Difficulty
Medium
Tags
二叉树
URL
https://blog.csdn.net/qq_17550379/article/details/95861409
Star
给你一棵二叉树的根节点 root，找出这棵树的 每一棵 子树的 平均值 中的 最大 值。
子树是树中的任意节点和它的所有后代构成的集合。
树的平均值是树中节点值的总和除以节点数。
示例：
notion imagenotion image
输入：[5,6,1]
输出：6.00000
解释：
以 value = 5 的节点作为子树的根节点，得到的平均值为 (5 + 6 + 1) / 3 = 4。
以 value = 6 的节点作为子树的根节点，得到的平均值为 6 / 1 = 6。
以 value = 1 的节点作为子树的根节点，得到的平均值为 1 / 1 = 1。
所以答案取最大值 6。
提示：
  1. 树中的节点数介于 1 到 5000之间。
  1. 每个节点的值介于 0 到 100000 之间。
  1. 如果结果与标准答案的误差不超过 10^-5，那么该结果将被视为正确答案。

法 1 信息传递

思路
后序遍历，向上传递 当前子树节点个数 和 当前子树 个节点之和。然后在每个节点计算
题解
class Solution:
    def maximumAverageSubtree(self, root: TreeNode) -> float:
    if root is None:
        return 0
    self.res = root.val
    self.helper(root)
    return self.res
    
    def helper(self, root):
        if root is None:
            return [0, 0]
        l = self.helper(root.left)
        r = self.helper(root.right)
        
        temp = [l[0]+r[0]+root.val, l[1]+r[1] + 1]
        
        self.res = max(self.res, temp[0] / temp[1])
        
        return temp