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

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 values of all nodes of the current layer can be obtained 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.
/ * * *@param {TreeNode} root
 * @return {number[][]}* /
var levelOrder = 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;
    result.push([]); // Store an array in result to store the node values of the current layer
    const currentIndex = result.length - 1; // Cache the index of the array that stores the current layer's data

    // 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();

      // Store the current layer's data to result
      result[currentIndex].push(node.val);

      // If the child node exists, the child node is enqueued as the node of the next levelnode.left && queue.push(node.left); node.right && queue.push(node.right); }}return result;
};
Copy the code