在每个树行中找最大值-515

[sl1673495]

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

[Nice-PLQ]

function largestValues(root) {
  if (!root) return [];

  const queue = [root];
  const result = [];

  while(queue.length > 0) { // 一层一层遍历
    let len = queue.length;
    let max = -Infinity;
    while(len > 0) { // 将每一层的节点都遍历完
      const node = queue.shift();
      max = Math.max(max, node.val);
      if (node.left) {
        queue.push(node.left);
      }

      if (node.right) {
        queue.push(node.right);
      }

      len--;
    }
    result.push(max);
  }

  return result;
};