剑指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;
};