企业官网建设流程全解析

• 教程
• 文档

给定一棵二叉树的根节点root，返回层数最深的叶子节点的和——这是 LeetCode 第 1302 题「层数最深叶子节点的和」 的核心诉求，难度为中等，Tag 为「DFS」、「BFS」、「树的遍历」。本文以「宫水三叶的刷题日记」刷穿 LeetCode 系列中该题的官方题解为骨架，完整保留其 BFS / DFS 双解法在 Java、C++、Python、TypeScript 四种语言下的实现，并结合本仓库（LogicStack-LeetCode）中同一系列的同主题题解（如 1161. 最大层内元素和、513. 找树左下角的值），深入剖析“按层统计”这一树遍历经典套路的原理与工程细节。读完本文，你将掌握：如何用 BFS 层序遍历一次性拿到“最深一层”的和，如何用 DFS + 哈希表实现等价逻辑，以及两类解法在时间、空间复杂度上的取舍。

题目回顾：最深一层叶子之和

先明确问题定义：

给你一棵二叉树的根节点root，请你返回层数最深的叶子节点的和。

注意题意的两个关键点：

1. “叶子节点”：左右子树均为空的节点才算叶子；
2. “层数最深”：所有叶子节点中，深度最大的那一层。也就是说，只要某个节点不是叶子（还有孩子），即便它位于更深层的祖先路径上，也不会计入。

示例 1：

输入：root = [1,2,3,4,5,null,6,7,null,null,null,null,8] 输出：15

最后一层为第 4 层，节点为7和8，和为7 + 8 = 15。

示例 2：

输入：root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5] 输出：19

最深层为第 4 层，节点为9、1、4、5，和为9 + 1 + 4 + 5 = 19。

数据约束：

• 树中节点数目在范围[1, 10^4]之间；
• 1 <= Node.val <= 100（所有节点值均为正整数，因此不需要像 1161. 最大层内元素和 那样用极小值初始化最大值比较）。

从数据范围看，n最大为10^4，两种遍历方案（BFS / DFS）都足以在极短时间内通过。

解法一：BFS 层序遍历，逐层累加并记录最大深度

BFS（广度优先搜索）天然按“层”推进，是本题最直观的解法。

核心思路

用队列维护待访问节点，每次先记录当前队列长度sz，这一长度就是“当前层”的节点数。随后一次性弹出sz个节点，完成一整层的处理：

1. 将该层所有节点值累加进map[depth]（以深度为键、层和为值的哈希表）；
2. 把每个节点的左右孩子（若存在）入队，构成下一层；
3. 处理完一整层后，depth++。

当队列为空时，遍历结束，depth - 1就是最大深度，map.get(depth - 1)即为答案。

这里的关键点在于以层为单位消费队列：int sz = d.size()必须在外层循环一开始就固定下来，而不是在内部循环中动态取d.size()——因为内部循环中不断有新节点入队，队列长度会持续变化，只有提前快照sz才能精确隔离出“当前层”。

四种语言实现

Java 代码：

class Solution { public int deepestLeavesSum(TreeNode root) { Map<Integer, Integer> map = new HashMap<>(); Deque<TreeNode> d = new ArrayDeque<>(); d.addLast(root); int depth = 0; while (!d.isEmpty()) { int sz = d.size(); while (sz-- > 0) { TreeNode node = d.pollFirst(); map.put(depth, map.getOrDefault(depth, 0) + node.val); if (node.left != null) d.addLast(node.left); if (node.right != null) d.addLast(node.right); } depth++; } return map.get(depth - 1); } }

C++ 代码：

class Solution { public: int deepestLeavesSum(TreeNode* root) { if (!root) return 0; queue<TreeNode*> d; unordered_map<int, int> map; d.push(root); int depth = 0; while (!d.empty()) { int sz = d.size(); while (sz-- > 0) { TreeNode* node = d.front(); d.pop(); map[depth] += node->val; if (node->left) d.push(node->left); if (node->right) d.push(node->right); } depth++; } return map[depth - 1]; } };

Python 代码：

class Solution: def deepestLeavesSum(self, root: Optional[TreeNode]) -> int: if not root: return 0 d = deque([root]) depth_map = {} depth = 0 while d: sz = len(d) for _ in range(sz): node = d.popleft() depth_map[depth] = depth_map.get(depth, 0) + node.val if node.left: d.append(node.left) if node.right: d.append(node.right) depth += 1 return depth_map[depth - 1]

TypeScript 代码（使用数组模拟队列，he/ta双指针）：

function deepestLeavesSum(root: TreeNode | null): number { const map: Map<number, number> = new Map<number, number>() const stk: TreeNode[] = new Array<TreeNode>(10010) let he = 0, ta = 0, depth = 0 stk[ta++] = root while (he < ta) { let sz = ta - he while (sz-- > 0) { const node = stk[he++] if (!map.has(depth)) map.set(depth, 0) map.set(depth, map.get(depth) + node.val) if (node.left != null) stk[ta++] = node.left if (node.right != null) stk[ta++] = node.right } depth++ } return map.get(depth - 1) };

TypeScript 版本使用定长数组（长度为10010，略大于最大节点数10^4）配合头尾指针模拟队列，避免了shift()的 O(n) 开销，是刷题中常见的“手写队列”优化手法，与本仓库 515. 在每个树行中找最大值 的 BFS 模板一脉相承。

复杂度分析

• 时间复杂度：$O(n)$，每个节点恰好入队、出队一次；
• 空间复杂度：$O(n)$，队列最多容纳一层的节点数，最坏情况（如满二叉树的最后一层）为 $O(n)$，哈希表同样为 $O(n)$。

变体思路：不存哈希表，滚动累加

如果只关心“最深一层”，其实可以进一步压缩：层序遍历天然从浅到深，第depth层处理完之后，下一层一定更深。因此可以放弃哈希表，只维护一个变量，在进入每一层时将其重置为 0，整层累加后保存为该层的和，遍历结束后，最后一次保存的和就是最深一层的和。这是“滚动更新”思路，代码更短、内存更省，但与本文题解记录的“全层和哈希表”相比，少了一份“随时可取任意层和”的灵活性。二者均属于本仓库 Index/BFS.md 索引中“树的层序遍历”一类题目的通解变体。

解法二：DFS 深度优先，哈希表按深度归组求和

BFS 按层推进，DFS 则按“路径”推进。虽然 DFS 不天然分层，但只要在递归时把当前深度depth作为参数传递，同样可以完成按层统计。

核心思路

定义递归函数dfs(root, depth)：

1. 若root为空，直接返回；
2. 用max = Math.max(max, depth)维护全局最大深度；
3. 将当前节点值累加进哈希表map[depth]；
4. 递归处理左右孩子，深度 +1。

整棵树遍历完成后，map.get(max)就是最大深度那一层的元素和，即答案。

相比 BFS，DFS 的优点在于不需要额外的队列结构，借助系统调用栈即可完成遍历；代价是需要同时维护“最大深度”和“按深度求和”两份状态。当depth == max时，map[max]恰好只包含最深层节点——由于题意只统计叶子节点，而“层数最深的叶子”所在层上不可能再有其他更深节点，因此该层所有节点都是叶子，直接对该层求和即可，无需逐个判断叶子身份。

四种语言实现

Java 代码（使用成员变量保存全局状态）：

class Solution { Map<Integer, Integer> map = new HashMap<>(); int max; public int deepestLeavesSum(TreeNode root) { dfs(root, 0); return map.get(max); } void dfs(TreeNode root, int depth) { if (root == null) return ; max = Math.max(max, depth); map.put(depth, map.getOrDefault(depth, 0) + root.val); dfs(root.left, depth + 1); dfs(root.right, depth + 1); } }

C++ 代码：

class Solution { public: unordered_map<int, int> map; int maxv = 0; int deepestLeavesSum(TreeNode* root) { dfs(root, 0); return map[maxv]; } void dfs(TreeNode* root, int depth) { if (!root) return; maxv = max(maxv, depth); map[depth] += root->val; dfs(root->left, depth + 1); dfs(root->right, depth + 1); } };

Python 代码：

class Solution: def __init__(self): self.mapping = {} self.maxv = 0 def deepestLeavesSum(self, root: TreeNode) -> int: self.dfs(root, 0) return self.mapping.get(self.maxv, 0) def dfs(self, root: TreeNode, depth: int) -> None: if not root: return self.maxv = max(self.maxv, depth) self.mapping[depth] = self.mapping.get(depth, 0) + root.val self.dfs(root.left, depth + 1) self.dfs(root.right, depth + 1)

TypeScript 代码：

const map: Map<number, number> = new Map<number, number>() let max: number function deepestLeavesSum(root: TreeNode | null): number { map.clear() max = 0 dfs(root, 0) return map.get(max) }; function dfs(root: TreeNode | null, depth: number): void { if (root == null) return max = Math.max(max, depth) if (!map.has(depth)) map.set(depth, 0) map.set(depth, map.get(depth) + root.val) dfs(root.left, depth + 1) dfs(root.right, depth + 1) }

注意 Python 版本将mapping与maxv保存在__init__中，这是为了让dfs递归调用时共享状态；TypeScript 版本在入口处显式map.clear()与max = 0，保证多次调用（如测试框架重复执行用例）时状态不残留。

复杂度分析

• 时间复杂度：$O(n)$，每个节点被访问一次；
• 空间复杂度：$O(n)$，递归栈深度最坏为链状树的 $O(n)$，哈希表同样为 $O(n)$。

从仓库视角看：本题与“按层统计”系列题的家族关系

本题属于“树遍历 + 按层聚合”这一经典题型。在本仓库（LogicStack-LeetCode）中，同族题目还有：

它们共享同一套“BFS 以sz = d.size()快照分层 / DFS 携带depth参数”的模板。具体到本题的 BFS 实现：int sz = d.size()后一次性消费整层，与本仓库 515. 在每个树行中找最大值 中“单次 BFS 逻辑将整一层的元素进行出队，维护当前层最大值”的手法完全一致；而 DFS 版本“哈希表按深度归组 + 全局变量记录最大深度”的思路，也与 515. 在每个树行中找最大值 的 DFS 解法如出一辙——足见这类题目在思路上是高度可迁移的。

从仓库索引看，本题同时收录于 Index/BFS.md（推荐指数 🤩🤩🤩🤩）与 Index/DFS.md（推荐指数 🤩🤩🤩🤩），是“一题双解”的代表题目，非常适合用来巩固树遍历基本功。

两种解法对比与选择建议

选择建议：当题目本身与“层”强相关（如本题“最深一层”、1161. 最大层内元素和）时，BFS 语义最直接；当题目与“路径”强相关（如 1022. 从根到叶的二进制数之和）时，DFS 携带路径状态更自然。而“DFS + 深度哈希表”作为通用兜底方案，在两类题目中都能改写成功——这也是本仓库 Index/DFS.md 将大量“树的遍历”题目归入同一 Tag 的原因。

小结

LeetCode 1302 是一道“外表简单、内里有料”的树遍历题：

• BFS 路线：层序遍历天然给出分层信息，sz = d.size()快照 + 深度哈希表即可锁定最深一层；
• DFS 路线：递归携带depth，配合“全局最大深度 + 按深度累加哈希表”，在遍历结束后直接取map[max]；
• 两种方案时间复杂度均为 $O(n)$，空间复杂度均为 $O(n)$，在10^4节点规模下均绰绰有余。

本题的完整源码与四语言实现收录于本仓库 LeetCode/1301-1310/1302. 层数最深叶子节点的和（中等）.md，同系列树遍历题解可在 Index/BFS.md、Index/DFS.md 与 Index/树的搜索.md 中按 Tag 继续查阅。掌握“按层聚合”这一套路后，无论题目换成“最大层和”“每行最大值”还是“最底层最左值”，都能在几分钟内完成迁移。

• 教程
• 文档