1120. Maximum Average Subtree - Explanation
Description
Given the root of a binary tree, return the maximum average value of a subtree of that tree. Answers within 10⁻⁵ 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.00000Explanation:
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.00000Constraints:
- The number of nodes in the tree is in the range
[1, 10⁴]. 0 <= Node.val <= 10⁵
1. Postorder Traversal
class Solution:
# for each node in the tree, we will maintain three values
class State:
def __init__(self, nodes, sum_val, max_average):
# count of nodes in the subtree
self.node_count = nodes
# sum of values in the subtree
self.value_sum = sum_val
# max average found in the subtree
self.max_average = max_average
def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:
return self.max_average(root).max_average
def max_average(self, root):
if root is None:
return self.State(0, 0, 0)
# postorder traversal, solve for both child nodes first.
left = self.max_average(root.left)
right = self.max_average(root.right)
# now find nodeCount, valueSum and maxAverage for current node `root`
node_count = left.node_count + right.node_count + 1
sum_val = left.value_sum + right.value_sum + root.val
max_average = max(
(1.0 * sum_val) / node_count, # average for current node
max(right.max_average, left.max_average) # max average from child nodes
)
return self.State(node_count, sum_val, max_average)Time & Space Complexity
- Time complexity:
- Space complexity:
Where is the number of nodes in the tree