队列+宽搜(BFS)-515.在每个树行中找最大值-力扣(LeetCode)

白天的黑夜

发布于 2025-10-22 17:29:49

3400

代码可运行

文章被收录于专栏：leetcode题目解析和知识分享leetcode题目解析和知识分享

运行总次数：0

代码可运行

一、题目解析

1、在每一层中找到该层的最大

2、val的范围[-2^31，2^31-1]

二、算法原理

解法：层序遍历+变量记录最大值

具体过程：

1、先创建queue队列存储节点的指针，一个vector用于存储最大值

2、入根，如果为空则直接返回vector，不为空则入根到队列中

3、循环进行层序遍历

1、统计队列中的元素个数，该个数为层序遍历的次数

2、定义一个变量并赋值MIN_INT，因为val的范围[-2^31，2^31-1]

3、开始层序遍历，取队头元素，判断其val是否大于记录最大值变量

4、入孩子

5、层序遍历结束后，将最大值加入到vector中

4、返回vector

这是queue的成员函数，若想详细了解，请移步链接自行查看

链接：queue - C++ Reference

三、代码示例

class Solution {
public:
    vector<int> largestValues(TreeNode* root)
    {
        vector<int> v;
        queue<TreeNode*> qt;//创建队列
        if(root) qt.push(root);//入根
        else return v;//如果root为空，返回v(v没初始化也为空)
        //层序遍历
        while(qt.size())
        {
            int num = qt.size();//计算队列中的元素个数
            TreeNode* tmp;
            int maxint = INT_MIN;//由于val的范围是[-2^31,2^31-1]，不能简单赋值为0
            while(num--)
            {
                tmp = qt.front();//取队头
                qt.pop();
                if(tmp->val>maxint)//maxint记录每层的最大值
                    maxint = tmp->val;
                if(tmp->left) qt.push(tmp->left);//入孩子
                if(tmp->right) qt.push(tmp->right);
            }
            v.push_back(maxint);//插入最大值
        }
        return v;
    }
};