NeetCode #403LC-1120MediumTreesNC Algo100
← Back to All Problems#403 · #1120 · Maximum Average Subtree(子树的最大平均值)
📌 Problem Statement & Constraints
Given the root of a binary tree, return the maximum average value of any subtree. A subtree is a node plus all its descendants, and its average is the sum of its values divided by its node count. Constraints: the number of nodes is in
[1, 5000], 0 <= Node.val <= 10^5.💡 Core Algorithmic Approaches
- A post-order DFS returns
(sum, count)for each subtree. - The average is
sum / count, which is a candidate answer at every node. - The parent combines the children's sums and counts.
- An alternative computes the maximum sum per node count and divides at the end, avoiding repeated division.
💻 Benchmark Python3 Implementation
class Solution:
def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:
self.best = 0.0
def dfs(node: Optional[TreeNode]):
"""Return (subtree sum, subtree node count)."""
if not node:
return (0, 0)
ls, lc = dfs(node.left)
rs, rc = dfs(node.right)
s = ls + rs + node.val
c = lc + rc + 1
self.best = max(self.best, s / c)
return (s, c)
dfs(root)
return self.best⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each node is visited once.
💾 Space Complexity
O(h) for the recursion stack.
⚠️ Interview Pitfalls & Follow-ups
- Returning only the average: the parent needs the sum and count separately to compute its own average.
- Comparing averages across different subtree sizes: that is exactly what the problem asks for, so comparing the averages directly is correct -- but do not compare sums.
- Forgetting the
Nonecase: it must contribute(0, 0), not affect the count. - Initialising
bestto 0: values are non-negative here, so 0 is a safe lower bound; with negative values you would need-infinity.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.