⚡Flashcard Drill➔
NeetCode #459LC-515MediumTrees
← Back to All Problems

#459 · #515 · Find Largest Value in Each Tree Row(在每个树行中找最大值)

📌 Problem Statement & Constraints

Given the root of a binary tree, return an array of the largest value in each level. Constraints: the number of nodes is in [0, 10^4], -2^31 <= Node.val <= 2^31 - 1.

💡 Core Algorithmic Approaches

  1. A level-order traversal with a frozen level size collects each level's nodes.
  2. Take the maximum within each level.
  3. Initialise the per-level maximum to -infinity so negative values are handled correctly.
  4. Both BFS and a depth-indexed DFS work; BFS is the more direct expression.

💻 Benchmark Python3 Implementation

class Solution:
    def largestValues(self, root: Optional[TreeNode]) -> List[int]:
        from collections import deque
        if not root:
            return []
        res = []
        q = deque([root])
        while q:
            n = len(q)
            mx = float("-inf")             # handles all-negative levels
            for _ in range(n):
                node = q.popleft()
                mx = max(mx, node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            res.append(mx)
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): every node is visited once.
💾 Space Complexity
O(w) for the widest level.

⚠️ Interview Pitfalls & Follow-ups

  • Initialising the maximum to 0: values can be negative, so -infinity is required.
  • Not freezing the level size: the levels would merge.
  • Appending to res inside the inner loop: it would record one entry per node.
  • Using a DFS without tracking depth: the level grouping would be lost.
⚡
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