一.题目
515. 在每个树行中找最大值 – 力扣（LeetCode）
二.思路讲解
2.1 思路讲解
本题要求找出二叉树每一层的最大值，本质仍是层序遍历（BFS） 的应用。
-
核心思路：使用队列进行层序遍历，在遍历每一层时，记录当前层的最大值。
-
处理负数：由于节点值可能为负数，因此初始化每层最大值时不能使用 0 或 -1，而应设置为理论最小值（如 INT_MIN）。
三.代码演示
/**
* 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) {}
* };
*/
class Solution {
public:
vector<int> largestValues(TreeNode* root)
{
vector<int> ret;
if(root == nullptr) return ret;
queue<TreeNode*> q;
q.push(root);
while(q.size())
{
int sz = q.size();//获取本层元素
int cur = INT_MIN;//记录最大值
for(int i = 0;i < sz;i++)
{
TreeNode* t = q.front();
q.pop();
cur = max(cur,t->val);
if(t->left != nullptr) q.push(t->left);
if(t->right != nullptr) q.push(t->right);
}
ret.push_back(cur);
}
return ret;
}
};
四.代码讲解
一、数据结构与初始化
-
ret：整型数组，用于存储每一层的最大值。
-
q：队列，用于按层顺序暂存待处理的节点，保证节点按层从左到右依次处理。
-
边界处理：如果根节点 root 为空，直接返回空结果集。
二、主循环：逐层处理
当队列不为空时，表示还有节点未处理，继续循环。
1. 记录当前层节点数
int sz = q.size();
此时队列中存放的恰好是当前层的所有节点（上一层的子节点已全部入队），sz 即为本层节点个数。
2. 初始化当前层最大值
由于节点值可能为负数，不能使用 0 或 -1 作为初始值，而应设置为理论最小值 INT_MIN（C++ 中 #include <climits> 提供），确保无论实际值多大或多小，都能被正确比较。
3. 遍历当前层节点
循环 sz 次：
-
取出队头节点 t，并将其值 t->val 与当前最大值 cur 比较，更新 cur。
-
若左子节点存在，将其入队；若右子节点存在，也将其入队。
4. 存储本层最大值
将计算得到的 cur 加入结果数组 ret。
三、关键细节
-
负数的正确处理：使用 INT_MIN 初始化每层最大值，确保即使该层所有节点值均为负数，也能正确选出最大值。
五、流程图
