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

内容简介

本文详细解析了力扣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 deepeSTLeavesSum(TreeNode* root) {
        maxdepth(root, 0); // 先计算最大深度
        return summaxdepth(root, 0); // 再求最深叶子节点的和
    }
};

复杂度分析

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

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

优化方向

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

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

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

总结

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