Construct a tree data structuretreeThat is as follows:

const tree = {
  val: "F".left: {
    val: "B".left: {
      val: "A".left: null
    },
    right: {
      val: "D".left: {
        val: "C"
      },
      right: {
        val: "E"}}},right: {
    val: "G".right: {
      val: "I".left: {
        val: "H"}}}};Copy the code

The former sequence traversal

/** * traversal, root -- left -- right *@param {*} root 
 * @param {*} arr 
 */
const preOrder = function (root, arr = []) {
  if(! root)return arr;
  arr.push(root.val); // Save the root node
  preOrder(root.left, arr); // Iterate over the left subtree
  preOrder(root.right, arr); // Iterate over the right subtree
  return arr;
}
console.log(preOrder(tree)); // ['F', 'B', 'A', 'D', 'C', 'E', 'G', 'I', 'H']
Copy the code

In the sequence traversal

/** * in order traversal, left - right - root *@param {*} root 
 * @param {*} arr 
 */
const inOrder = function (root, arr = []) {
  if(! root)return arr;
  inOrder(root.left, arr); // Iterate over the left subtree
  arr.push(root.val); // Save the root node in the middle
  inOrder(root.right, arr); // Iterate over the left subtree
  return arr;
}
console.log(inOrder(tree)); // ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']
Copy the code

After the sequence traversal

/** * after traversal, left - right - root *@param {*} root 
 * @param {*} arr 
 */
const postOrder = function (root, arr = []) {
  if(! root)return arr;
  postOrder(root.left, arr);
  postOrder(root.right, arr);
  arr.push(root.val);
  return arr;
}
console.log(postOrder(tree));  ['A'.'C'.'E'.'D'.'B'.'H'.'I'.'G'.'F']
Copy the code

Note: The above three traversals are depth-first traversals

Breadth-first traversal

/** * breadth-first traversal, returns a one-dimensional array *@param {*} root 
 */
var BFS = function (root) {
  let queue = []; // first in, first out
  let result = [];
  queue.push(root);
  while (queue.length > 0) {
    let node = queue.shift(); // Fetch the header element
    result.push(node.val);

    if (node.left) {
      queue.push(node.left);
    }
    if(node.right) { queue.push(node.right); }}return result;
};

console.log(BFS(tree)); // ['F', 'B', 'G', 'A', 'D', 'I', 'C', 'E', 'H']
Copy the code

Sequence traversal

What is sequential traversal? In simple terms, sequential traversal means layering the binary tree and traversing each layer from left to right: at first glance, the traversal order is the same as BFS, and we can use BFS directly to get the result of sequential traversal. However, sequence traversal requires different input results than BFS. Sequential traversal requires us to differentiate each layer, which returns a two-dimensional array. The BFS traversal results in a one-dimensional array that does not distinguish between each layer. Author: nettee

Link: leetcode-cn.com/problems/bi… Copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.

/** * order traversal, returns a two-dimensional array containing each layer of elements *@param {*} root 
 */
function levelOrder(root) {
  let queue = []; //
  let result = [];
  queue.push(root);
  while (queue.length > 0) {
    let size = queue.length; // The number of current levels
    let levelArr = [];
    for (let i = 0; i < size; i++) { // Create a nested loop that processes data at each level
      const node = queue.shift();
      levelArr.push(node.val);
      if (node.left) {
        queue.push(node.left);
      }
      if (node.right) {
        queue.push(node.right);
      }
    }
    result.push(levelArr);
  }
  return result;
}

console.log(levelOrder(tree));
/ * the results as follows: [[' F '], [' B ', 'G'], [' A ', 'D', 'I'], [' C ', 'E', 'H']] * /
Copy the code