Problem Description
Given the root of a binary tree, return the maximum average value of a subtree of that tree. Answers within 10-5 of the actual answer will be accepted.
A subtree of a tree is any node of that tree plus all its descendants.
The average value of a tree is the sum of its values, divided by the number of nodes.
Example 1:
Input: root = [5,6,1] Output: 6.00000 Explanation: For the node with value = 5 we have an average of (5 + 6 + 1) / 3 = 4. For the node with value = 6 we have an average of 6 / 1 = 6. For the node with value = 1 we have an average of 1 / 1 = 1. So the answer is 6 which is the maximum.
Example 2:
Input: root = [0,null,1] Output: 1.00000
Constraints:
- The number of nodes in the tree is in the range
[1, 10^4]. 0 <= Node.val <= 10^5
The description was taken from https://leetcode.com/problems/maximum-average-subtree/.
Problem Solution
#O(N) Time, O(N) Space
class Solution:
def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:
max_mean = 0
def postorder(node:int) -> list[int]:
nonlocal max_mean
if not node:
return [0,0]
left = postorder(node.left)
right = postorder(node.right)
sub_sum = left[1] + right[1] + node.val
sub_count = left[0] + right[0] + 1
mean = sub_sum/sub_count
max_mean = max(max_mean, mean)
return [sub_count, sub_sum]
postorder(root)
return max_meanProblem Explanation
This question is very similar to Balanced Binary Tree.
When doing binary tree questions, it is important to ask "whose information do we need first?" This will let us know whether to perform a preorder traversal if we need the left side first, an inorder traversal if we need the top first, or a postorder if we need the bottom first.
In order for a node to know the size of the subtree that they are the root of, it would first need to know the size of the subtrees that its children are the root of. The same goes for the subtree sum.
This tells us that we will need to visit each child node first before their parent nodes, so we will use a postorder traversal.
What we will do is perform a postorder traversal Depth-First Search on the tree and during each node function call, we will take the sum and count of each child subtree below it so that we can calculate the mean. We will then compare that mean to the maximum we have seen, and if it is greater then we will update the maximum to it.
Let's start by initializing the maximum mean to zero.
The problem constraints say that the node values can start at zero so in the case that there is only one node in the tree and its value is zero, this is the smallest mean we could have.
max_mean = 0
Next, let's create our recursive postorder function.
The function will take a node as an argument and will return a pair list where the first index is the count of nodes in its subtree and the second index is the overall sum of nodes in its subtree.
def postorder(node:int) -> list[int]:
Within our function, we will reference our nonlocal maximum mean. In Python, this specifies that this new count variable's scope expands beyond this inner function.
nonlocal max_mean
The base case we will set is if the current node is null, then we have finished a DFS path and have no more nodes to sum or count.
If this is the case then we will return zeros for our pair and begin bringing this information up to the node's parents.
if not node:
return [0,0]
Otherwise, we will continue moving down the left and right children to keep counting.
left = postorder(node.left)
right = postorder(node.right)
Once the DFS yoyo has come back up to the current node, we will calculate the total sum of the current subtree and the current count, including the current node.
sub_sum = left[1] + right[1] + node.val
sub_count = left[0] + right[0] + 1
We will take that sum and count to calculate a mean, compare that mean value to the maximum value saved and then we will return the subtree count and sum to this node's parent.
mean = sub_sum/sub_count
max_mean = max(max_mean, mean)
return [sub_count, sub_sum]
Now that we have our function built, we just need to make the initial call on the root then return the maximum mean that was calculated.
postorder(root)
return max_mean