Original link: leetcode-cn.com/problems/fi…

Answer:

  1. This problem can use BFS, layer by layer traversal binary tree.
  2. The traversal is done using queues in which nodes of each tier are stored in order.
  3. In each cycle, the nodes of the current layer in the queue are taken out successively, and the maximum value of the current layer can be obtained through continuous comparison in this cycle.
  4. At the same time, the child nodes of each node in the current layer are successively stored at the end of the queue, waiting for the next traversal processing.
  5. Repeat steps 3 and 4 continuously to complete the sequence traversal and find the maximum value of each line.
/ * * *@param {TreeNode} root
 * @return {number[]}* /
var largestValues = function (root) {
  let result = []; // Storage sequence traversal result
  let queue = []; // Use queues for sequential traversal. Queues store all nodes of each tier
  root && queue.push(root); // If the tree exists, it is traversed

  // Iterate over the queue until the queue is empty
  while (queue.length) {
    // Cache the number of nodes in the current layer to avoid changing the number of nodes during the queue operation, which may affect the number of for loops
    const queueLength = queue.length;
    let max = -Infinity; // Store the maximum value of the current layer

    // Loop out nodes as many times as there are nodes in the current layer
    // queueLength must be fixed because the next tier node is queued during the loop
    for (let i = 0; i < queueLength; i++) {
      // Unqueue the nodes of the current layer in turn
      const node = queue.shift();

      // Continuously compare and store the maximum value of the current layer
      max = Math.max(node.val, max);

      // If the child node exists, the child node is enqueued as the node of the next level
      node.left && queue.push(node.left);
      node.right && queue.push(node.right);
    }

    // Store the maximum value of the current layer into result
    result.push(max);
  }

  return result;
};
Copy the code