层数最深叶子节点的和 (Deepest Leaves Sum)

1. 题目描述

题目背景： 在二叉树的深度特性研究中，寻找“最深处”的节点是基础任务。本题要求在给定二叉树中，定位所有处于最大深度的叶子节点，并计算它们的权值总和。

任务描述： 给你一棵拥有 $n$ 个节点的二叉树。请你返回层数最深的叶子节点的和。 所谓“层数最深”，是指该节点到根节点的路径长度（节点数）最大。

输入格式：

1. 第一行包含一个整数 $n$（$1 \le n \le 10^4$），表示节点总数。
2. 接下来的 $n$ 行，每行包含三个整数 $v_i, l_i, r_i$，分别表示第 $i$ 个节点的权值、左孩子节点的编号、右孩子节点的编号。
3. 节点编号从 $1$ 到 $n$。如果某个孩子节点不存在，则编号为 $0$。根节点固定为编号 $1$。

输出格式： 一个整数，表示层数最深的叶子节点的权值和。

样例 1： 输入：

8
1 2 3
2 4 5
3 0 6
4 7 0
5 0 0
6 0 8
7 0 0
8 0 0

输出：

15

(解释：最大深度为 4，第 4 层的节点是 7 和 8，和为 7 + 8 = 15)

样例 2： 输入：

11
6 2 3
7 4 5
8 6 7
2 8 0
7 9 10
1 0 0
3 0 11
9 0 0
1 0 0
4 0 0
5 0 0

输出：

19

(注：这里第 11 行变成了 5 0 0，总节点数改为 11，删除了第 12 行。此时最深层为第 4 层，和为 19)

2. 预备知识点

1. 二叉树遍历：
   • BFS（广度优先搜索）：逐层扫描，最后一层处理到的节点即为最深节点。
   • DFS（深度优先搜索）：递归探测深度，维护全局最大深度。
2. 树的深度计算：理解根节点深度为 1（或 0），向下递增。
3. 累加器逻辑：当发现更深的层级时，需要重置当前的累加值。

3. 启发式思维引导

请拿出你的草稿纸，思考以下两个方案的推导过程：

方案一：BFS 的“层级覆盖”法（一趟搜索）

• 观察：BFS 是按层推进的。
• 推理：
  1. 当我们要处理新的一层时，上一层的和已经没用了。
  2. 在处理每一层前，将 currentSum 清零。
  3. 把该层所有节点值加到 currentSum。
  4. 当队列为空，不再有下一层时，当前的 currentSum 就是答案。
• 复杂度分析：
  • 时间：$O(n)$，每个点进出队一次。
  • 空间：$O(w)$，$w$ 为树的最大宽度。

方案二：DFS 的“动态更新”法（一趟递归）

• 观察：我们需要在搜索过程中记住见过的“最深位置”。
• 推理：
  1. 定义全局变量 maxDep（最大深度）和 totalSum（结果）。
  2. 每到一个节点 $u$，已知其深度为 $d$。
  3. 情况 A：$d > maxDep$。说明找到了新大陆！更新 maxDep = d，并把 totalSum 重置为当前节点值。
  4. 情况 B：$d == maxDep$。说明又找到一个最深层的节点。totalSum += node.val。
  5. 情况 C：$d < maxDep$。不用管。
• 复杂度分析：
  • 时间：$O(n)$。
  • 空间：$O(h)$，$h$ 为树的高度（系统栈开销）。

4. 算法流程图 (基于 BFS 一趟搜索逻辑)

为了保证 Mermaid 渲染正常，我们避免在节点内使用特殊字符。

graph TD
    Start(开始) --> QueueInit(初始化队列Q并加入根节点1)
    QueueInit --> GlobalSum(定义ans变量用于存储当前层总和)
    
    GlobalSum --> LoopOuter{队列Q是否为空}
    LoopOuter -- 否 --> LevelReset(将ans重置为0)
    LoopOuter -- 是 --> Output(输出ans并结束)
    
    LevelReset --> GetSize(获取当前队列大小SZ)
    GetSize --> LoopInner{循环SZ次}
    
    LoopInner -- 迭代中 --> PopNode(弹出队首节点U)
    PopNode --> AddVal(将U的权值加到ans)
    AddVal --> CheckLeft{U有左孩子吗}
    CheckLeft -- 有 --> PushL(左孩子入队)
    CheckLeft -- 无 --> CheckRight(U有右孩子吗)
    PushL --> CheckRight
    CheckRight -- 有 --> PushR(右孩子入队)
    CheckRight -- 无 --> LoopInner
    
    LoopInner -- 循环结束 --> LoopOuter

5. 读题关键词总结

在 NOI 竞赛中，遇到此类题目要注意捕捉以下“题眼”：

1. “最深” (Deepest)：

   • 暗示你需要关注 最大深度 (Max Depth)。
   • 实现策略：BFS 的最后一层或 DFS 记录最大深度。

2. “叶子节点” (Leaves)：

   • 本题虽说“最深叶子”，但实际上最深层的所有节点一定都是叶子（否则它们就不是最深的）。
   • 警示：如果题目要求的是“所有层的所有叶子之和”，逻辑则完全不同。

3. “和” (Sum)：

   • 提示需要一个 累加器 (Accumulator)。
   • 优化建议：在 BFS 中，不需要存储每一层的和，只需要在每层开始前清空累加器，保留到最后的那一份就是最深层的。

4. 数据范围 $N=10^4$：

   • 属于中型规模。
   • 建议：这种量级下 BFS 和 DFS 表现差异不大。但如果 $N$ 达到 $10^5$ 且树极度倾斜，DFS 需要注意系统栈大小（NOI 默认栈空间通常较大，但仍需谨慎）。

教练提示：在考场上，BFS 的逻辑往往比 DFS 维护全局深度更不容易出错，尤其是处理“层级重置”这类逻辑时。加油！