内容简介

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

算法思路

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

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

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

代码实现 （带详细注释）

                      class Solution {
public:
    int depth = 0; // 存储树的最大深度
    
    // 计算树的最大深度
    void maxdepth(TreeNode* root, int dep) {
        if (root) {
            // 更新最大深度
            if (dep > depth) 
                depth = dep;
            // 递归处理左右子树，深度+1
            maxdepth(root->left, dep + 1);
            maxdepth(root->right, dep + 1);
        }
    }
    
    // 求最深叶子节点的和
    int summaxdepth(TreeNode* root, int dep) {
        if (!root)
            return 0; // 空节点返回0
        if (dep == depth) 
            return root->val; // 找到最深叶子节点
        // 递归求左右子树的和
        return summaxdepth(root->left, dep + 1) + summaxdepth(root->right, dep + 1);
    }
    
    // 主函数
    int deepe
                      
                        STL
                      
                      eavesSum(TreeNode* root) {
        maxdepth(root, 0); // 先计算最大深度
        return summaxdepth(root, 0); // 再求最深叶子节点的和
    }
};
                    

复杂度分析

‌ 时间复杂度 ‌：O(n)，两次遍历共访问每个节点两次

‌空间复杂度‌：O(h)，递归 栈 空间取决于树的高度

优化 方向

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

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

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

总结

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