---
title: "1302. Deepest Leaves Sum"
url: "https://laigary.com/interview/coding/1302-deepest-leaves-sum"
type: "note"
section: "coding"
date: "2025-03-25"
updated: "2026-07-28"
tags: ["Tree", "Breadth-First Search"]
---

# 1302. Deepest Leaves Sum

[1302\. Deepest Leaves Sum](https://leetcode.com/problems/deepest-leaves-sum/)

求最深那一層所有節點的總和。

## 思路

一樣是 [102. 層序遍歷](/interview/coding/102-binary-tree-level-order-traversal) 的骨架換一行。這題有一個很好用的性質：

**分層 BFS 走完之後，最後處理的那一層必定是最深的那一層。** 所以根本不需要先算樹高，也不用判斷誰是葉節點 —— 一路往下走，走到佇列空了為止，手上留著的那層就是答案。

「最深的葉節點」聽起來要先找深度，但換成層序來看，它只是「最後一層」而已。

## 解題方向

### 一、把每一層算出來，只留最新的

```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 deepestLeavesSum(self, root: Optional[TreeNode]) -> int:
        
        if not root:
            return 0
        
        levels = []
        q = deque([root])
        
        while q:
            size = len(q)
            curr = []
            for _ in range(size):
                node = q.popleft()
                curr.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            if levels:
                levels.pop()
            levels.append(curr)
        
        return sum(levels[-1])
```

`if levels: levels.pop()` 是關鍵的一行 —— 每次要放新的一層之前，先把上一層丟掉。所以 **`levels` 從頭到尾只會有一個元素**，永遠是「目前為止最深的那一層」。

（換句話說，這個版本並不是真的把每一層都存下來。如果真的全存，空間會是 $O(n)$ 而不是 $O(w)$。）

### 二、直接用一個變數

既然 `levels` 永遠只有一個元素，那就不需要 list 了：

```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 deepestLeavesSum(self, root: Optional[TreeNode]) -> int:
        
        q = deque([root])
        result = root.val
        
        while q:
            size = len(q)
            curr = []
            for _ in range(size):
                node = q.popleft()
                curr.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            
            result = sum(curr)
        
        return result
                
```

`result` 每一層都被覆蓋掉，迴圈結束時留下的就是最後一層的總和。第二版更能表達「我只在乎最後一層」這件事。

`result = root.val` 這個初始值其實用不到（第一輪迴圈就會覆蓋掉它），寫它只是為了讓變數先存在。另外這版沒有 `if not root` 的保護，`root.val` 會直接炸 —— 這題保證至少有一個節點所以沒問題，但跟版本一的處理方式不一致，值得留意。

**還可以更精簡**：`curr` 這個陣列也不需要，直接 `result = 0` 然後在內層迴圈裡累加就好。三個版本的差別只是「留下多少不需要的中間結果」。

## 補充

**也可以用 DFS 做**：把深度當參數傳下去，維護 `max_depth` 和 `total`，走到更深的層就把 `total` 歸零重算。跟 BFS 版的差別是 BFS 靠「最後一層」這個結構性質，DFS 得自己比較深度。

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

| 題目 | 在那一層裡做什麼 |
|---|---|
| [102. Level Order](/interview/coding/102-binary-tree-level-order-traversal) | 收集整層 |
| [199. Right Side View](/interview/coding/199-binary-tree-right-side-view) | 只取最後一個 |
| [515. Largest Value in Each Row](/interview/coding/515-find-largest-value-in-each-tree-row) | 取 max |
| 1302 | **求和，只留最後一層** |
| [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$ 是節點數。兩個版本的複雜度相同 —— 因為版本一的 `levels` 靠 `pop()` 維持在長度 1，並沒有真的存下整棵樹。