链接：https://leetcode.cn/problems/deepest-leaves-sum/solution/-by-xun-ge-v-u1y5/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 

题目

示例

思路

解题思路
对于树的相关问题基本上都可以使用递归解决，对于递归能解决的问题那么迭代也基本上是可以的

• 递归->深度优先搜索
• 迭代->广度优先搜索

【深度优先搜索】
使用递归搜索每一个节点，以高度为判断条件：

• 高度未达到当前已检索的最深高度->不处理
• 高度正好达到当前已检索的最深高度->累加
• 高度超过当前已检索的最深高度->重新累加

最后输出累加和即可

【广度优先搜索】
使用迭代进行树的层次遍历，累加最后一层即可
对于迭代可以不需要那么多的判断，因为层次遍历本身就是以树的高度为条件

代码

【深度优先搜索】

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


void dfs(struct TreeNode* node, int level, int* maxLevel, int* sum) {
    if (node == NULL) {
        return;
    }
    if (level > *maxLevel) {//高度超过当前已检索的最深高度->重新累加
        *maxLevel = level;
        *sum = node->val;
    } else if (level == *maxLevel) {//高度正好达到当前已检索的最深高度->累加
        *sum += node->val;
    }
    //高度未达到当前已检索的最深高度->不处理
    dfs(node->left, level + 1, maxLevel, sum);
    dfs(node->right, level + 1, maxLevel, sum);
}

int deepestLeavesSum(struct TreeNode* root){
    int maxLevel = -1;//当前最高高度
    int sum = 0;//累和
    dfs(root, 0, &maxLevel, &sum);
    return sum;
}


作者：xun-ge-v
链接：https://leetcode.cn/problems/deepest-leaves-sum/solution/-by-xun-ge-v-u1y5/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

【广度优先搜索】 

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


int deepestLeavesSum(struct TreeNode* root){
    int sum;
    struct TreeNode * queue[10000];//标准层次遍历过程，可以把这个摸版背下来
    int left = 0;
    int right = 0;
    queue[right++] = root;
    while(left < right)
    {
        int r = right;
        sum = 0;
        while(left < r)
        {
            sum += queue[left]->val;
            if(queue[left]->left)
            {
                queue[right++] = queue[left]->left;
            }
            if(queue[left]->right)
            {
                queue[right++] = queue[left]->right;
            }
            left++;
        }
    }
    return sum;
}

作者：xun-ge-v
链接：https://leetcode.cn/problems/deepest-leaves-sum/solution/-by-xun-ge-v-u1y5/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。