剑指Offer|LCR 044.在每个树行中找最大值
LCR 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
法1：队列
分析：
初始化变量：当前层数的节点数current，下一层的节点数量next均为0，定义空的queue。
root不为空，直接加入队列。current设置为1个结点。
遍历queue，将root出队列，求出当前层次最大值，如果有左右孩子的话，就将左右孩子入队列，孩子是下一层节点，所以next需要++。当current为0的话，说明这一层的结点数遍历完了，所以将max也就是这一层的最大值存入result中，更新一下max、current和next。
var largestValues = function(root) {let current = 0; // 当前层数的节点数let next = 0; // 下一层的节点数量let queue = []; // 用来存放待遍历的节点if (root !== null) {queue.push(root);current = 1;}let result = [];let max = -Infinity;// 广度优先遍历整个树while (queue.length > 0) {let node = queue.shift();current--;max = Math.max(max, node.val);if (node.left !== null) {queue.push(node.left);next++;}if (node.right !== null) {queue.push(node.right);next++;}if (current === 0) {result.push(max);max = -Infinity;current = next;next = 0;}}return result;
};