层数最深叶子节点的和 图解题解

这道题到底在问什么

输入

[50,30,80,20,40,60,90,null,null,70,85]

输出

155

输入

[42]

输出

42

最优解：一步一步想明白

1. 3记住「队列按层展开,每层把 s 重新算一遍,循环结束时 s 就是最深层的和」,下面逐帧套它。
2. 4按深度分层先找感觉:同一深度的节点是同一层。一层层往下,最深的是第 4 层的 70 和 85(蓝色),它们下面再没有节点。我们要的就是这最深一层的和。
3. 5本层 1 个节点进入第 1 层,队列里是 [50]。把 s 清零,再从左到右扫这一整层、边扫边累加。
4. 6加上 50从队首取出 50(红色高亮),把它加进本层和 s:0 加 50 得到 50。
5. 750 → 30,8050 加完了。把它的非空孩子 30、80(蓝色)加入下一层,目前下一层攒到了 [30、80]。
6. 8第 1 层和 50第 1 层扫完,本层和 s 是 50。它的孩子组成了下一层,所以 s 之后还会被下一层重新算一遍,目前先把 50 当作「最后一层的和」记着。
7. 9本层 2 个节点进入第 2 层,队列里是 [30、80]。把 s 清零,再从左到右扫这一整层、边扫边累加。
8. 10加上 30从队首取出 30(红色高亮),把它加进本层和 s:0 加 30 得到 30。
9. 1130 → 20,4030 加完了。把它的非空孩子 20、40(蓝色)加入下一层,目前下一层攒到了 [20、40]。
10. 12加上 80从队首取出 80(红色高亮),把它加进本层和 s:30 加 80 得到 110。
11. 1380 → 60,9080 加完了。把它的非空孩子 60、90(蓝色)加入下一层,目前下一层攒到了 [20、40、60、90]。
12. 14第 2 层和 110第 2 层扫完,本层和 s 是 110。它的孩子组成了下一层,所以 s 之后还会被下一层重新算一遍,目前先把 110 当作「最后一层的和」记着。
13. 15本层 4 个节点进入第 3 层,队列里是 [20、40、60、90]。把 s 清零,再从左到右扫这一整层、边扫边累加。
14. 16加上 20从队首取出 20(红色高亮),把它加进本层和 s:0 加 20 得到 20。
15. 1720 是叶子20 是叶子,没有孩子可加,下一层暂时还是 [空]。
16. 18加上 40从队首取出 40(红色高亮),把它加进本层和 s:20 加 40 得到 60。
17. 1940 → 70,8540 加完了。把它的非空孩子 70、85(蓝色)加入下一层,目前下一层攒到了 [70、85]。
18. 20加上 60从队首取出 60(红色高亮),把它加进本层和 s:60 加 60 得到 120。
19. 2160 是叶子60 是叶子,没有孩子可加,下一层暂时还是 [70、85]。
20. 22加上 90从队首取出 90(红色高亮),把它加进本层和 s:120 加 90 得到 210。
21. 2390 是叶子90 是叶子,没有孩子可加,下一层暂时还是 [70、85]。
22. 24第 3 层和 210第 3 层扫完,本层和 s 是 210。它的孩子组成了下一层,所以 s 之后还会被下一层重新算一遍,目前先把 210 当作「最后一层的和」记着。
23. 25本层 2 个节点进入第 4 层,队列里是 [70、85]。把 s 清零,再从左到右扫这一整层、边扫边累加。
24. 26加上 70从队首取出 70(红色高亮),把它加进本层和 s:0 加 70 得到 70。
25. 2770 是叶子70 是叶子,没有孩子可加,下一层暂时还是 [空]。
26. 28加上 85从队首取出 85(红色高亮),把它加进本层和 s:70 加 85 得到 155。
27. 2985 是叶子85 是叶子,没有孩子可加,下一层暂时还是 [空]。
28. 30第 4 层和 155第 4 层扫完,本层和 s 是 155。这一层每个节点都没有孩子,队列即将空,它就是最深一层,s = 155 就是最终答案。
29. 31答案 = 155四层的和依次是 50、110、210、155。最深的是第 4 层(金色 70、85),它的和 155 就是答案。特别注意:第 3 层的和 210 反而更大,但我们要的是最深那层,不是和最大的那层。回头看,就是一遍按层 BFS,每层重算一次 s,循环结束时 s 自然停在最深层,时间 O(n)。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List, Optional
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 = [root]
        s = 0
        while q:
            s = sum(n.val for n in q)
            q = [c for n in q for c in (n.left, n.right) if c]
        return s

#include <algorithm>
#include <climits>
#include <functional>
#include <queue>
#include <vector>
using namespace std;
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution { public: int deepestLeavesSum(TreeNode* root){ queue<TreeNode*> q; q.push(root); int sum=0; while(!q.empty()){ sum=0; for(int sz=q.size();sz--;){ auto n=q.front(); q.pop(); sum+=n->val; if(n->left)q.push(n->left); if(n->right)q.push(n->right);} } return sum; } };

import java.util.*;
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; }
}
class Solution { public int deepestLeavesSum(TreeNode root){ Queue<TreeNode> q=new ArrayDeque<>(); q.offer(root); int sum=0; while(!q.isEmpty()){ sum=0; for(int sz=q.size();sz>0;sz--){ TreeNode n=q.poll(); sum+=n.val; if(n.left!=null)q.offer(n.left); if(n.right!=null)q.offer(n.right);} } return sum; } }

复杂度

面试官可能追问