C++ 队列 宽度优先搜索 BFS 力扣 515. 在每个树行中找最大值 每日一题
文章目录
一、题目描述
题目链接：力扣 515. 在每个树行中找最大值
题目描述：
示例 1：
输入：root = [1,3,2,5,3,null,9]
输出：[1,3,9]
示例 2：
输入：root = [1,2,3]
输出：[1,3]
提示：
树中节点数目在范围 [0, 10⁴] 内
-2³¹ <= Node.val <= 2³¹ - 1
二、为什么这道题值得你花几分钟弄懂？
这道题是BFS层序遍历的经典进阶应用，是大厂面试中考察“分层遍历+层内统计”的高频题。它在基础层序遍历的核心逻辑上，增加了“层内最大值统计”的规则，既能检验我们对BFS分层逻辑的掌握程度，又能考察我们在遍历过程中进行数值计算的能力，是夯实树遍历基础、提升逻辑拓展能力的必做题。
题目核心价值:
- 基础能力的延伸：在二叉树层序遍历的“分层”核心上，新增“层内极值统计”逻辑，检验我们是否真正理解分层遍历的本质，而非死记硬背代码。
- 逻辑灵活性的体现：同一套BFS框架下，仅通过简单的“层内值比较+最大值记录”就能实现需求，训练我们“在通用框架上定制化需求”的思维。
- 面试的“基础筛选题”：基础层序遍历是入门题，而层内找最大值是基础题的变形，能区分“只会写固定代码”和“能灵活调整逻辑”的候选人。
- 边界场景的再训练：同样需要处理空树、单节点树、满二叉树等场景，进一步强化我们考虑问题的全面性。
- 代码简洁性的平衡：在不破坏BFS核心逻辑的前提下，用最少的代码实现层内最大值统计，契合面试中“简洁且易读”的代码评分标准。
面试考察的核心方向:
- BFS分层逻辑的迁移能力：能否将基础层序遍历的思路无缝迁移，并适配“层内统计”的需求。
- 逻辑拓展能力：能否在基础遍历逻辑上，快速添加“层内最大值初始化+逐值比较”的拓展逻辑。
- 数值边界处理：是否能意识到用
INT_MIN初始化最大值的合理性，以及处理负数节点值的场景。 - 复杂度分析：能否准确分析算法的时间和空间复杂度，理解“层内比较”不会增加整体时间复杂度。
掌握这道题，既能巩固BFS分层遍历的核心，又能训练“基础逻辑+定制化统计”的解题思路。
三、算法原理
本题的核心算法是 “基于队列的BFS分层遍历 + 层内最大值统计”，在基础层序遍历的框架上，仅增加“层内最大值初始化”和“逐节点值比较更新最大值”两步操作，逻辑清晰且易于理解。
- 初始化一个队列，把二叉树的根节点入队（若根节点为空，直接返回空结果）。
- 初始化一个结果数组，用于存储每一层的最大值。
- 当队列不为空时，执行以下操作：
- 记录当前队列的大小（即当前层的节点数
n）。 - 初始化当前层的最大值变量
max_val为整型最小值（INT_MIN），确保能覆盖所有节点值的边界情况。 - 循环
n次，依次取出队列头部的节点：- 将当前节点值与
max_val比较，更新max_val为两者中的较大值。 - 若节点有左子节点，将左子节点入队；若有右子节点，将右子节点入队（为下一层遍历做准备）。
- 将当前节点值与
- 将当前层的最大值
max_val加入结果数组。
- 记录当前队列的大小（即当前层的节点数
- 队列为空时，遍历完成，返回最终结果数组。
这个思路的本质是：用BFS完成分层遍历，在遍历每一层的过程中同步统计最大值，以最小的代码改动适配“层内找最大值”的需求。
模拟过程
我们用示例1完整模拟，帮你直观理解每一步的队列状态和最大值统计过程。
场景：示例1 二叉树 [1,3,2,5,3,null,9]
初始状态：
- 队列
q = [1] - 最终结果
ret = []
| 步骤 | 队列状态 | 当前层节点数(n) | 当前层最大值(max_val) | 节点值比较过程 | ret变化 |
|---|---|---|---|---|---|
| 1 | [1] | 1 | 1 | 1 → max_val=1 | [1] |
| 2 | [3,2] | 2 | 3 | 3→max_val=3 → 2→max_val保持3 | [1,3] |
| 3 | [5,3,9] | 3 | 9 | 5→max_val=5 → 3→max_val保持5 → 9→max_val=9 | [1,3,9] |
| 4 | [] | 0 | - | 队列空，结束遍历 | 不变 |
细节注意
- 最大值初始化：必须用
INT_MIN（需包含<climits>头文件）初始化，不能用0，否则无法正确处理全负数的二叉树（比如节点值为[-5,-3,-8]的情况）。 - 子节点入队顺序：二叉树层序遍历需先入队左子节点、再入队右子节点，不影响最大值统计，但这是层序遍历的标准操作。
- 边界条件：空树直接返回空数组，避免后续操作空指针；单节点树直接返回
[val]，无需额外处理。
常见错误与避坑
- 最大值初始化错误：二叉树节点的取值是有负数的，用0或1初始化最大值，会导致全负数节点的二叉树统计结果错误。
- 忘记处理空树：直接操作空根节点会触发空指针异常。
- 层内节点数获取时机错误：在循环过程中获取队列大小，而非循环前，导致统计的节点数混入下一层节点。
- 最大值更新逻辑错误：在节点入队后才更新最大值，导致当前节点值未被统计。
四、代码实现
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */#include<vector>#include<queue>#include<climits>// 包含INT_MIN所需的头文件usingnamespace std;classSolution{public: vector<int>largestValues(TreeNode* root){// 存储每一层的最大值 vector<int> ret;// 边界条件：空树直接返回空数组if(root ==nullptr)return ret;// 标准队列存储二叉树节点，效率优于vector模拟 queue<TreeNode*> q; q.push(root);// 队列非空则继续遍历while(!q.empty()){// 记录当前层的节点数（循环前获取，避免混入下一层节点）int n = q.size();// 初始化当前层最大值为整型最小值，覆盖所有数值边界int max_val = INT_MIN;// 遍历当前层的所有节点for(int i =0; i < n; i++){// 取出队头节点 TreeNode* tmp = q.front(); q.pop();// 核心：更新当前层的最大值 max_val =max(max_val, tmp->val);// 二叉树子节点入队：先左后右，保证层序遍历顺序if(tmp->left !=nullptr) q.push(tmp->left);if(tmp->right !=nullptr) q.push(tmp->right);}// 将当前层的最大值加入结果数组 ret.push_back(max_val);}return ret;}};代码细节说明
- 队列的实现：使用C++标准库的
queue<TreeNode*>（push入队、front()取队头、pop()出队），相比vector模拟队列效率更高（queue的pop操作时间复杂度为O(1)）。 - 核心逻辑：
- 外层
while循环：控制层的遍历，队列非空则继续； - 内层
for循环：遍历当前层的所有节点，逐值比较更新最大值，并将子节点入队； - 最大值统计：用
max函数比较当前节点值和已记录的最大值，确保每一层能找到最大的节点值。
- 外层
- 数值边界处理：用
INT_MIN初始化最大值，确保能正确处理节点值为负数的场景（比如节点值为[-1,-2,-3]时，仍能统计出-1作为第一层最大值）。
复杂度分析
- 时间复杂度：O(n)。n是二叉树的节点数，每个节点入队、出队各一次（O(n)）；层内最大值比较操作总次数为O(n)（每个节点仅参与一次比较），因此整体时间复杂度仍为O(n)。
- 空间复杂度：O(n)。最坏情况下（完美二叉树的最后一层），队列存储的节点数为n/2，空间复杂度为O(n)；结果数组存储每一层的最大值，空间复杂度为O(h)（h为树的高度），整体空间复杂度为O(n)。
五、总结
- 核心逻辑：BFS分层遍历 + 层内最大值统计是解决本题的核心，在遍历每一层节点的过程中同步更新最大值是最高效的方式。
- 细节要点：用
INT_MIN初始化层内最大值以覆盖负数场景，层内节点数需在循环前获取，子节点需“先左后右”入队。 - 代码优化：标准库
queue比vector模拟队列效率更高，层内比较操作不影响整体时间复杂度。
六、下题预告
下一篇我们一起学习优先级队列（堆）在算法题中的应用，攻克 力扣 1046. 最后一块石头的重量。
喵~ 能啃完这道二叉树最大宽度喵，宝子你真的真的真的很棒喵～😼 要是对分层统计的逻辑、队列操作的时机还有小疑问喵，或者有更丝滑的解题思路喵，都可以甩到评论区喵，我看到会第一时间把问题给这个博主的喵～
别忘了点个赞、关个注～(๑˃̵ᴗ˂̵)و 你的支持就是博主继续肝优质算法内容的最大动力喵～我们下道题，不见不散喵～
