The biggest value in each row
Find the largest value on every level of a tree by keeping a running maximum for the row while the queue is processed. About 12 minutes.
One number per row
The row-by-row walk is a frame that you can fill with any per-row calculation. For the largest value in each row, you do not need a list of the row. Keep a single running maximum.
At the start of each row, set it to something smaller than any value. For each node of the row, compare and keep the larger. When the row is done, add the maximum to the answer.
best = -inf
for _ in range(len(q)):
node = q.popleft()
best = max(best, node.val)- result
- [1]
Row one has only 1, so its maximum is 1.
Same frame, other questions
Change the accumulator and the same walk answers other questions. A running sum gives the total of each row. A counter gives the width of each row. Keeping the first value gives the leftmost node, and the last gives the rightmost.
Values can be negative, so start the maximum at the first node of the row or at negative infinity, never at zero.
out.append(best)
A row holds -4, -9 and -2. What should the maximum start as, so the answer is right?
- ANegative infinity, or the first node's value
- B0
- C1
Show the answer
Negative infinity, or the first node's value. Any starting value that is not above every real value keeps the comparison honest.
Largest value in each tree row
Given the root of a binary tree, return an array of the largest value in each level, from the top level to the bottom. An empty tree gives an empty array.
root = [1, 3, 2, 5, 3, null, 9] → [1, 3, 9]
0 ≤ number of nodes ≤ 10,000 · -2,147,483,648 ≤ node.val ≤ 2,147,483,647