Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

We discussed the structure and traversal of binary tree before, introduced the depth first traversal (DFS) and breadth first traversal (BFS) recursive and non-recursive implementation, the implementation of binary tree before, after order traversal (using DFS), today we discuss the order traversal of binary tree (using BFS).

DFS versus BFS traversal process:

102 Sequence traversal of binary trees

Leetcode-cn.com/problems/bi…

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).

This must be breadth-first traversal (BFS)

Let’s review the breadth-first traversal code we implemented earlier

function BFS(root) {
  const queue = [];
  queue.unshift(root);

  while (queue.length > 0) {
    root = queue.pop();
    if (root.left) queue.unshift(root.left);
    if(root.right) queue.unshift(root.right); }}Copy the code

The sequence traversed here is breadth-first traversal, but our sequential traversal requires each node of the level to be in an array. So we’re going to output a two-dimensional array, so we’re going to change the breadth-first traversal code

  • The BFS traversal results in:[1, 2, 3, 4, 5, 6, 7, 8, 9]
  • The result of sequence traversal is:[[1], [2, 3], [4, 5, 6], [7, 8, 9]

We’ve added a loop that allows us to get all the elements out of the queue each time, creating a layer array of elements

function BFS(root) {
  const queue = [];
  queue.unshift(root);
  
  while (queue.length > 0) {+let len = queue.length;
+   for (let i = 0; i < len; i++) {
      root = queue.pop();
      if (root.left) queue.unshift(root.left);
      if(root.right) queue.unshift(root.right); +}}}Copy the code

【 例 句 】 Breadth-first search

In the final complete code, I don’t just need to create a result array to store the result, and then create a level level ordinal group to store the sequence of each layer traversal

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {TreeNode} root
 * @return {number[][]}* /

function levelOrder(root) {
  if(! root)return [];
  const result = [];
  const queue = [];
  queue.unshift(root);

  while (queue.length > 0) {
    let len = queue.length;
    let level = [];
    for (let i = 0; i < len; i++) {
      root = queue.pop();
      level.push(root.val);
      if (root.left) queue.unshift(root.left);
      if (root.right) queue.unshift(root.right);
    }
    result.push(level);
  }
  return result;
}
Copy the code

Image source force buckle question solution