LeetCode·每日一题·1161.最大层内元素和·层次遍历

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

题目

 

示例

 

思路

解题思路
对于树的相关问题使用递归基本上都可以解决
对于本题我们需要寻找层内元素之和 最大 的那几层（可能只有一层）的层号，并返回其中 最小 的那个。
那么首先需要对每一层的元素进行遍历求和，对于树的每一层元素遍历，无疑使用层次遍历最为方便，对于层次遍历可以用递归也可以使用迭代，对于层次遍历迭代更方便理解，这里使用迭代实现层次遍历

具体实现
树的层次遍历需要使用队列保存每一层的元素，我们遍历树，将树的每一层元素存入队列，然后按每层弹出队列中元素，同时保存每层元素的和，并且判断弹出元素是否存在子节点，存在子节点时存入队列，每层弹出后保存最大值和对应层数

代码

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


int maxLevelSum(struct TreeNode* root){
    struct TreeNode * ans[10000];//队列
    int left = 0;
    int right = 0;
    ans[right++] = root;//头结点入队
    int max = INT_MIN;//最大值层和
    int storey = 1;//当前位于第几层
    int s = -1;//最大值位于第几层
    while(left < right)//层次遍历
    {
        int sum = 0;//当前层元素和
        int r = right;
        while(left < r)//按层弹出元素
        {
            sum += ans[left]->val;
            if(ans[left]->left)//弹出元素判断是否存在子元素
            {
                ans[right++] = ans[left]->left;
            }
            if(ans[left]->right)
            {
                ans[right++] = ans[left]->right;
            }
            left++;
        }
        if(sum > max)//保存最大值层
        {
            max = sum;
            s = storey;
        }
        storey++;
    }
    return s;
}

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

时间空间复杂度