---
title: "515. Find Largest Value in Each Tree Row"
url: "https://laigary.com/interview/coding/515-find-largest-value-in-each-tree-row"
type: "note"
section: "coding"
date: "2025-03-25"
updated: "2026-07-28"
tags: ["Tree", "Breadth-First Search"]
---

# 515. Find Largest Value in Each Tree Row

[515\. Find Largest Value in Each Tree Row](https://leetcode.com/problems/find-largest-value-in-each-tree-row/)

回傳每一層的最大值。

## 思路

跟 [199. Right Side View](/interview/coding/199-binary-tree-right-side-view) 一樣，是 [102. 層序遍歷](/interview/coding/102-binary-tree-level-order-traversal) 換一行 —— 骨架完全相同，只把「收集整層」改成「這一層取 max」。

分層的關鍵（先固定 `len(queue)` 再跑迴圈）見 102。

### 初始值一定要用 `-inf`，不能用 0

這是這題唯一真正會出錯的地方。節點值可以是負的（題目的範圍是 $-2^{31}$ 到 $2^{31}-1$），如果把每層的 `currMax` 初始化成 0，遇到整層都是負數就會回傳 0：

```text
        -1
       /  \
     -2   -3

正確（用 -inf）：[-1, -2]
用 0 初始化：    [0, 0]      ← 全錯
```

「用 0 當最大值的初始值」是很常見的反射動作，但它其實假設了「答案至少是 0」。只要題目沒保證非負，就得用 `float('-inf')`，或者乾脆拿這一層的第一個元素當初始值。

## 解題方向

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def largestValues(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        ans = []
        q = deque([root])

        while q:
            currMax = float('-inf')
            for _ in range(len(q)):
                node = q.popleft()
                currMax = max(currMax, node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            ans.append(currMax)
        
        return ans
```

這裡用 `for _ in range(len(q))` 而不是 `for i in ...`，因為這題不在乎節點在層裡的位置，只在乎值 —— 跟 199 需要 `i` 來判斷「是不是最後一個」剛好形成對照。

## 補充

**同一個骨架的家族**：

| 題目 | 在那一層裡做什麼 |
|---|---|
| [102. Level Order](/interview/coding/102-binary-tree-level-order-traversal) | 收集整層 |
| [199. Right Side View](/interview/coding/199-binary-tree-right-side-view) | 只取最後一個 |
| 515 | **取 max** |
| [1302. Deepest Leaves Sum](/interview/coding/1302-deepest-leaves-sum) | 求和，只留最後一層 |
| [103. Zigzag Level Order](/interview/coding/103-binary-tree-zigzag-level-order-traversal) | 奇數層反轉 |
| [116](/interview/coding/116-populating-next-right-pointers-in-each-node) / [117](/interview/coding/117-populating-next-right-pointers-in-each-node-ii) | 把同層節點用 `next` 串起來 |

整理見 [Tree 遍歷模板](/interview/coding/tree-traversal-template)。

## 複雜度

- 時間 $O(n)$ — 每個節點進出佇列各一次
- 空間 $O(w)$ — `w` 是最寬那層的節點數，最壞 $O(n)$

其中 $n$ 是節點數，輸出的 `ans` 不計。