力扣1302题：层数最深叶子节点的和 - 递归双遍历解法详解

胡志明t

一、内容简介

本文详细解析了力扣1302题"层数最深叶子节点的和"的递归双遍历解法。通过先计算树的**深度，再求该深度所有节点值的和，展示了如何高效解决这类树结构问题。文章包含完整注释代码、算法思路讲解和复杂度分析，帮助读者掌握树遍历的**技巧。

二、算法思路

‌深度计算阶段‌：递归遍历树，记录**深度

‌求和阶段‌：再次递归遍历，累加深度等于**深度的节点值

‌双递归设计‌：先确定深度边界，再收集目标节点

三、代码实现（带详细注释）

1. class Solution {
   
2. public:
   
3.     int depth = 0; // 存储树的**深度
   
4.    
   
5.     // 计算树的**深度
   
6.     void maxdepth(TreeNode* root, int dep) {
   
7.         if (root) {
   
8.             // 更新**深度
   
9.             if (dep > depth)
   
10.                 depth = dep;
    
11.             // 递归处理左右子树，深度+1
    
12.             maxdepth(root->left, dep + 1);
    
13.             maxdepth(root->right, dep + 1);
    
14.         }
    
15.     }
    
16.    
    
17.     // 求最深叶子节点的和
    
18.     int summaxdepth(TreeNode* root, int dep) {
    
19.         if (!root)
    
20.             return 0; // 空节点返回0
    
21.         if (dep == depth)
    
22.             return root->val; // 找到最深叶子节点
    
23.         // 递归求左右子树的和
    
24.         return summaxdepth(root->left, dep + 1) + summaxdepth(root->right, dep + 1);
    
25.     }
    
26.    
    
27.     // 主函数
    
28.     int deepeSTLeavesSum(TreeNode* root) {
    
29.         maxdepth(root, 0); // 先计算**深度
    
30.         return summaxdepth(root, 0); // 再求最深叶子节点的和
    
31.     }
    
32. };

复制代码

四、优化方向

‌单次遍历解法‌：在遍历时同时记录当前深度和对应节点值的和

‌迭代实现‌：使用栈或队列替代递归

‌并行处理‌：对左右子树可考虑并行计算

五、总结

双递归解法清晰地分离了深度计算和求和的逻辑，虽然时间复杂度略高但思路直观。理解这种解法有助于掌握树问题的分层处理技巧。

来源：力扣1302题：层数最深叶子节点的和 - 递归双遍历解法详解