“This is the 14th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Hope is a good thing, maybe the best of things. And no good thing ever dies.

preface

In the previous several articles, I summarized the solution of the recursive and iterative way of the pre-order traversal, middle-order traversal and post-order traversal of the binary tree. Today, I will learn about its sequential traversal.

What is sequential traversal

Sequential traversal is better understood as printing the data stored in each node from top to bottom and left to right in a binary tree. The data structure is shown below:

Compare the four traversal modes:

  • A → B → D → C
  • Middle order traversal: B → D → A → C
  • Subsequent traversal: D → B → C → A
  • Sequence traversal: A → B → C → D

The title

Given a binary tree, return the values of nodes traversed in order. (That is, layer by layer, all nodes are accessed from left to right).

Example: binary tree: [3,9,20, NULL, NULL,15,7], 3 / \ 9 20 / \ 15 7 Returns the result of its sequence traversal: [[3], [9,20], [15,7]Copy the code

Add: leetcode-cn.com/problems/bi…

Ideas and Analysis

Use a variable to record the current layer

The subscript of the array is the current layer

If you are entering this layer for the first time,

Create an empty array

Otherwise, the node value is added to the array for that layer

Returns an array of

To sum up: each element of the queue records depth. An array of the same depth is returned

The problem solving

var levelOrder = function (root) { if (root == null) { return []; } let result = []; let queue = [root]; while (queue.length) { let levelSize = queue.length; // Let curLevelResult = []; For (let I = 0; i < levelSize; i++) { const node = queue.shift(); curLevelResult.push(node.val); if (node.left) queue.push(node.left); if (node.right) queue.push(node.right); } result.push(curLevelResult); } return result; };Copy the code

conclusion

If this article helped you, please like 👍 and follow ⭐️.

If there are any errors in this article, please correct them in the comments section 🙏🙏

Welcome to pay attention to my wechat public number, exchange technology together, wechat search 🔍 : “fifty years later”