1. 问题背景与理解
今天遇到一道挺有意思的二叉树题目——"1302 层数最深叶子节点的和"。简单来说，就是给定一棵二叉树，要求计算其最深一层叶子节点值的总和。这个问题看似简单，但实际考察了对二叉树遍历、深度计算和递归/迭代的理解。
举个例子，假设有这样一棵二叉树：
1 / \ 2 3 / \ \ 4 5 6 / \ 7 8在这棵树中，最深层是第4层，叶子节点是7和8，所以结果应该是7+8=15。
2. 解题思路分析
2.1 深度优先 vs 广度优先
面对这个问题，首先想到的是两种经典遍历方式：
- 深度优先搜索(DFS)：可以递归地遍历树，记录当前深度，当遇到更深节点时更新结果
- 广度优先搜索(BFS)：按层遍历，最后一层的节点和就是所求结果
提示：对于这种需要知道最深层的题目，BFS按层遍历的思路通常更直观
2.2 递归实现细节
如果用DFS递归实现，需要考虑几个关键点：
- 如何记录当前深度？
- 如何判断是否到达更深层？
- 如何累加最深层的节点值？
递归函数可以设计为：
def dfs(node, depth): nonlocal max_depth, total if not node: return if depth > max_depth: max_depth = depth total = node.val elif depth == max_depth: total += node.val dfs(node.left, depth+1) dfs(node.right, depth+1)2.3 迭代实现方案
BFS的迭代实现通常使用队列，可以这样处理：
- 初始化队列包含根节点
- 当队列不为空时：
- 记录当前层节点数
- 处理完当前层后，如果下一层非空则更新结果
- 否则当前层就是最深层，返回结果
3. 完整代码实现
3.1 Python递归解法
class Solution: def deepestLeavesSum(self, root: TreeNode) -> int: self.max_depth = 0 self.total = 0 def dfs(node, depth): if not node: return if depth > self.max_depth: self.max_depth = depth self.total = node.val elif depth == self.max_depth: self.total += node.val dfs(node.left, depth+1) dfs(node.right, depth+1) dfs(root, 0) return self.total3.2 Python迭代解法
from collections import deque class Solution: def deepestLeavesSum(self, root: TreeNode) -> int: if not root: return 0 queue = deque([root]) result = 0 while queue: level_size = len(queue) level_sum = 0 for _ in range(level_size): node = queue.popleft() level_sum += node.val if node.left: queue.append(node.left) if node.right: queue.append(node.right) result = level_sum return result3.3 复杂度分析
两种方法的时间复杂度都是O(N)，需要遍历所有节点：
- 递归：空间复杂度O(H)，H是树高（递归栈深度）
- 迭代：空间复杂度O(W)，W是树的最大宽度
4. 常见问题与优化
4.1 空树处理
两种实现都需要考虑空树的情况：
if not root: return 04.2 递归深度限制
对于非常深的树，Python默认递归深度可能不够（通常是1000），可以修改递归限制：
import sys sys.setrecursionlimit(100000)4.3 内存优化
对于BFS实现，可以在处理完一层后立即释放内存：
for _ in range(level_size): node = queue.popleft() # ...处理节点... del node # 显式释放内存5. 实际应用场景
这类二叉树深度相关的问题在实际中有多种应用：
- 文件系统目录深度统计
- 组织结构图层级分析
- 游戏AI中的决策树评估
- 网络路由跳数计算
我在实际项目中曾用类似方法分析过网站导航结构的深度，帮助优化用户体验。发现超过4层的导航结构会显著降低用户留存率，这个发现直接指导了我们的界面 redesign。
