⚡Flashcard Drill➔
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

  1. A post-order DFS returns (sum, count) for each subtree.
  2. The average is sum / count, which is a candidate answer at every node.
  3. The parent combines the children's sums and counts.
  4. 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 None case: it must contribute (0, 0), not affect the count.
  • Initialising best to 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.
🎯 Drill This Card Now➔

🧩 Related Trees Problems