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
- A level-order traversal with a frozen level size collects each level's nodes.
- Take the maximum within each level.
- Initialise the per-level maximum to
-infinityso negative values are handled correctly. - 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
-infinityis required. - Not freezing the level size: the levels would merge.
- Appending to
resinside 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.