算法日常・每日刷题--＜队列,宽搜＞4

LCR 044. 在每个树行中找最大值 - 力扣LeetCodeLCR 044. 在每个树行中找最大值 - 给定一棵二叉树的根节点 root 请找出该二叉树中每一层的最大值。 示例 1输入: root [1,3,2,5,3,null,9]输出: [1,3,9]解释: 1 / \ 3 2 / \ \ 5 3 9 示例 2输入: root [1,2,3]输出: [1,3]解释: 1 / \ 2 3示例 3输入: root [1]输出: [1]示例 4输入: root [1,null,2]输出: [1,2]解释: 1 \ 2 示例 5输入: root []输出: [] 提示 * 二叉树的节点个数的范围是 [0,104] * -231 Node.val 231 - 1 注意本题与主站 515 题相同 https://leetcode.cn/problems/find-largest-value-in-each-tree-row/ [https://leetcode.cn/problems/find-largest-value-in-each-tree-row/]https://leetcode.cn/problems/hPov7L/description/一、题目分析给定一棵二叉树根节点root按层遍历二叉树收集每一层节点的最大值最终返回存储每层最大值的数组。二叉树层序遍历BFS 广度优先搜索借助队列逐层处理每层单独遍历一遍遍历过程维护当前层最大值每层遍历结束后存入结果。示例 1二叉树分层第一层[1]→ 最大值1第二层[3,2]→ 最大值3第三层[5,3,9]→ 最大值9输出[1,3,9]二、算法思路详解边界处理根节点为空时直接返回空数组队列初始化创建队列将根节点入队开启层序循环分层循环每次循环先获取当前队列长度levelSize代表当前层节点数量单层遍历循环levelSize次逐个取出队首节点对比更新当前层最大值存在左 / 右子节点则入队作为下一层节点保存结果单层遍历完成将该层最大值存入结果数组队列为空时循环结束返回结果。/** * 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: vectorint largestValues(TreeNode* root) { vectorint ans; // 空树直接返回空数组 if(root nullptr) return ans; queueTreeNode* q; q.push(root); while(!q.empty()) { int levelSize q.size(); // 当前层节点总数 int maxNum INT_MIN; // 记录当前层最大值 // 遍历当前整层 for(int i 0; i levelSize; i) { TreeNode* cur q.front(); q.pop(); // 更新层最大值 if(cur-val maxNum) maxNum cur-val; // 左右子节点入队 if(cur-left) q.push(cur-left); if(cur-right) q.push(cur-right); } ans.push_back(maxNum); } return ans; } };