二叉树DFS问题：求最深叶子节点和的代码错误排查

原代码核心错误 #

1. 局部变量maxlvl完全无效：每次进入dfs函数都会重新初始化maxlvl = -1，根本无法跟踪遍历过程中的全局最大深度。导致每个节点的层级都会被判定为大于当前maxlvl，sum会被反复覆盖，最终结果完全错误。
2. 全局变量sum的副作用：全局变量会保留上一次函数调用的结果，若多次调用deepestLeavesSum，会出现累加残留的错误。

修正方案：用指针传递共享状态 #

我们需要在递归过程中共享两个关键状态：当前记录的最大深度、对应深度的节点和。通过指针将这两个变量传入递归函数，既避免全局变量的副作用，又解决局部变量无法跨递归共享的问题。

修正后的代码 #

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

void dfs(struct TreeNode *root, int lvl, int *max_lvl, int *sum) {
    if (root == NULL) return;
    
    // 当前节点深度大于已记录的最大深度，更新最大深度并重置求和值
    if (lvl > *max_lvl) {
        *max_lvl = lvl;
        *sum = root->val;
    } 
    // 当前节点深度等于最大深度，累加节点值
    else if (lvl == *max_lvl) {
        *sum += root->val;
    }
    
    dfs(root->left, lvl + 1, max_lvl, sum);
    dfs(root->right, lvl + 1, max_lvl, sum);
}

int deepestLeavesSum(struct TreeNode* root){
    int max_lvl = -1;
    int sum = 0;
    dfs(root, 0, &max_lvl, &sum);
    return sum;
}

关键调整说明 #

• 移除全局变量sum，改为在deepestLeavesSum中声明局部变量，通过指针传递给dfs，确保每次调用函数都是全新的计算状态。
• 新增max_lvl变量并通过指针传递，递归过程中持续更新全局最大深度，保证所有节点的深度对比都是基于整个二叉树的最大深度，而非单次递归的局部值。
• 递归逻辑清晰：遍历每个节点时，根据当前深度与最大深度的关系，要么重置求和值，要么累加节点值，最终得到最深叶子节点的数值和。

内容的提问来源于stack exchange，提问作者user20977916