Maximum Average Subtree

Problem Id: 1120 Difficulty: Medium Tag: Tree


Intuition

The average value of a sub-tree is total_sum / number_of_nodes. So we could use a DFS with 2 additional return values to solve this problem.

Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def maximumAverageSubtree(self, root: TreeNode) -> float:
        self.max_avg = float('-inf')
        self._helper(root)
        return self.max_avg

    def _helper(self, node):
        if node is None:
            return 0, 0
        l = self._helper(node.left)
        r = self._helper(node.right)
        s = l[0] + r[0] + node.val
        numbers = l[1] + r[1] + 1
        self.max_avg = max(self.max_avg, s / numbers)
        return s, numbers