515. Find Largest Value in Each Tree Row

515. Find Largest Value in Each Tree Row

回傳每一層的最大值。

思路

跟 199. Right Side View 一樣，是 102. 層序遍歷 換一行 —— 骨架完全相同，只把「收集整層」改成「這一層取 max」。

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

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

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

        -1
       /  \
     -2   -3

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

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

解題方向

# 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	收集整層
199. Right Side View	只取最後一個
515	取 max
1302. Deepest Leaves Sum	求和，只留最後一層
103. Zigzag Level Order	奇數層反轉
116 / 117	把同層節點用 next 串起來

整理見 Tree 遍歷模板。

複雜度

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

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