Open
Description
https://leetcode-cn.com/problems/find-largest-value-in-each-tree-row
您需要在二叉树的每一行中找到最大的值。
输入:
1
/ \
3 2
/ \ \
5 3 9
输出: [1, 3, 9]
思路
这是一道典型的 BFS 题目，BFS 的套路其实就是维护一个 queue 队列，在读取子节点的时候同时把发现的孙子节点 push 到队列中，但是先不处理，等到这一轮队列中的子节点处理完成以后，下一轮再继续处理的就是孙子节点了，这就实现了层序遍历，也就是一层层的去处理。
但是这里有一个问题卡住我了一会，就是如何知道当前处理的节点是哪个层级的，在最开始的时候我尝试写了一下二叉树求某个 index 所在层级的公式，但是发现这种公式只能处理「平衡二叉树」。
后面看题解发现他们都没有专门维护层级，再仔细一看才明白层级的思路：
其实就是在每一轮 while 循环里，再开一个 for 循环，这个 for 循环的终点是「提前缓存好的 length 快照」，也就是进入这轮 while 循环时，queue 的长度。其实这个长度就恰好代表了「一个层级的长度」。
缓存后，for 循环里可以安全的把子节点 push 到数组里而不影响缓存的当前层级长度。
另外有一个小 tips，在 for 循环处理完成后，应该要把 queue 的长度截取掉上述的缓存长度。一开始我使用的是 queue.splice(0, len)，结果速度只击败了 33%的人。后面换成 for 循环中去一个一个shift来截取，速度就击败了 77%的人。
/**
* @param {TreeNode} root
* @return {number[]}
*/
let largestValues = function (root) {
if (!root) return [];
let queue = [root];
let maximums = [];
while (queue.length) {
let max = Number.MIN_SAFE_INTEGER;
// 这里需要先缓存length 这个length代表当前层级的所有节点
// 在循环开始后 会push新的节点 length就不稳定了
let len = queue.length;
for (let i = 0; i < len; i++) {
let node = queue[i];
max = Math.max(node.val, max);
if (node.left) {
queue.push(node.left);
}
if (node.right) {
queue.push(node.right);
}
}
// 本「层级」处理完毕，截取掉。
for (let i = 0; i < len; i++) {
queue.shift();
}
// 这个for循环结束后 代表当前层级的节点全部处理完毕
// 直接把计算出来的最大值push到数组里即可。
maximums.push(max);
}
return maximums;
};