C++ 二叉树层序遍历：在每个树行中找最大值

常见错误与避坑

1. 最大值初始化错误：二叉树节点的取值是有负数的，用 0 或 1 初始化最大值，会导致全负数节点的二叉树统计结果错误。
2. 忘记处理空树：直接操作空根节点会触发空指针异常。
3. 层内节点数获取时机错误：在循环过程中获取队列大小，而非循环前，导致统计的节点数混入下一层节点。
4. 最大值更新逻辑错误：在节点入队后才更新最大值，导致当前节点值未被统计。

四、代码实现

#include <vector>
#include <queue>
#include <climits>

using namespace std;

/**
 * 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;
        
        // 标准队列存储二叉树节点，效率优于 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;
    }
};

代码细节说明

1. 队列的实现：使用 C++ 标准库的 queue<TreeNode*>（push 入队、front() 取队头、pop() 出队），相比 vector 模拟队列效率更高（queue 的 pop 操作时间复杂度为 O(1)）。
2. 核心逻辑：
   • 外层 while 循环：控制层的遍历，队列非空则继续；
   • 内层 for 循环：遍历当前层的所有节点，逐值比较更新最大值，并将子节点入队；
   • 最大值统计：用 max 函数比较当前节点值和已记录的最大值，确保每一层能找到最大的节点值。
3. 数值边界处理：用 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)。

五、总结

1. 核心逻辑：BFS 分层遍历 + 层内最大值统计是解决本题的核心，在遍历每一层节点的过程中同步更新最大值是最高效的方式。
2. 细节要点：用 INT_MIN 初始化层内最大值以覆盖负数场景，层内节点数需在循环前获取，子节点需'先左后右'入队。
3. 代码优化：标准库 queue 比 vector 模拟队列效率更高，层内比较操作不影响整体时间复杂度。