1302. Deepest Leaves Sum

──────────────────────────────────────────────────────────────────────

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

思路

一樣是 102. 層序遍歷的骨架換一行。這題有一個很好用的性質：

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

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

解題方向

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

# 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 了：

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

整理見 Tree 遍歷模板。

複雜度

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

其中 $n$ 是節點數。兩個版本的複雜度相同 —— 因為版本一的 levels 靠 pop() 維持在長度 1，並沒有真的存下整棵樹。