05、在每个树行中找最大值

这个题目其实只要会二叉树的层序遍历，解决起来非常简单的

题目链接：515. 在每个树行中找最大值 - 力扣（LeetCode）

题目描述

给定一棵二叉树的根节点 root，请找出该二叉树中每一层的最大值。

示例 1：

输入：root = [1,3,2,5,3,null,9]
输出：[1,3,9]

        1
       / \
      3   2
     / \   \
    5   3   9

解释：

• 第 1 层：最大值是 1
• 第 2 层：最大值是 3
• 第 3 层：最大值是 9

示例 2：

输入：root = [1,2,3]
输出：[1,3]

        1
       / \
      2   3

数据范围：

• 二叉树的节点个数的范围是 [0, 10^4]
• -2^31 <= Node.val <= 2^31 - 1

很简单，只需要层序遍历的时候，保存一下该层的最大值就好了

核心思路

1. 按层遍历二叉树
2. 在每一层中找出最大值
3. 将每层的最大值加入结果数组

二叉树层序遍历

算法思路

1. 使用队列进行层序遍历
2. 遍历每一层时，维护当前层的最大值
3. 将每层最大值加入结果数组

图解过程

以 root = [1,3,2,5,3,null,9] 为例：

        1
       / \
      3   2
     / \   \
    5   3   9

第 1 层：[1]           → 最大值：1
第 2 层：[3, 2]        → 最大值：3
第 3 层：[5, 3, 9]     → 最大值：9

结果：[1, 3, 9]

C++ 实现

#include <vector>
#include <queue>
#include <algorithm>
#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> result;

        // 特殊情况：空树
        if (root == nullptr) {
            return result;
        }

        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            int levelSize = q.size();
            int maxVal = INT_MIN;  // 初始化为最小值

            // 遍历当前层的所有节点
            for (int i = 0; i < levelSize; i++) {
                TreeNode* node = q.front();
                q.pop();

                // 更新当前层的最大值
                maxVal = max(maxVal, node->val);

                // 将子节点加入队列
                if (node->left) {
                    q.push(node->left);
                }
                if (node->right) {
                    q.push(node->right);
                }
            }

            // 将当前层的最大值加入结果
            result.push_back(maxVal);
        }

        return result;
    }
};

复杂度分析

时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点被访问一次。

空间复杂度：O(w)，其中 w 是二叉树的最大宽度（一层中最多的节点数）。队列中最多存储一层的节点。