实现二叉树前序、中序、后序遍历及广度优先遍历、层序遍历

85A0C626-F227-4d0e-85ED-7ACA838A5973.png

构造一个树的数据结构tree，如下：

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"
      }
    }
  }
};

前序遍历

/**
 * 前序遍历，根--左--右
 * @param {*} root 
 * @param {*} arr 
 */
const preOrder = function (root, arr = []) {
  if (!root) return arr;
  arr.push(root.val); // 先保存根节点
  preOrder(root.left, arr); // 遍历左子树
  preOrder(root.right, arr); // 遍历右子树
  return arr;
}
console.log(preOrder(tree)); // ['F', 'B', 'A', 'D', 'C', 'E', 'G', 'I', 'H']

中序遍历

/**
 * 中序遍历，左--右--根
 * @param {*} root 
 * @param {*} arr 
 */
const inOrder = function (root, arr = []) {
  if (!root) return arr;
  inOrder(root.left, arr); // 遍历左子树
  arr.push(root.val); // 中间保存根节点
  inOrder(root.right, arr); // 遍历左子树
  return arr;
}
console.log(inOrder(tree)); // ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']

后序遍历

/**
 * 后序遍历，左--右--根
 * @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']

注：上述三种遍历都是深度优先遍历

广度优先遍历

/**
 * 广度优先遍历，返回一维数组
 * @param {*} root 
 */
var BFS = function (root) {
  let queue = []; //JS数组实现队列，先进先出
  let result = [];
  queue.push(root);
  while (queue.length > 0) {
    let node = queue.shift(); // 取出头元素
    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']

层序遍历

什么是层序遍历呢？简单来说，层序遍历就是把二叉树分层，然后每一层从左到右遍历：

乍一看来，这个遍历顺序和 BFS 是一样的，我们可以直接用 BFS 得出层序遍历结果。然而，层序遍历要求的输入结果和 BFS 是不同的。层序遍历要求我们区分每一层，也就是返回一个二维数组。而 BFS 的遍历结果是一个一维数组，无法区分每一层。

作者：nettee
链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/solution/bfs-de-shi-yong-chang-jing-zong-jie-ceng-xu-bian-l/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

270462CB-2DF9-4f74-987C-B1F17D0CC847.png

/**
 * 层序遍历，返回二维数组，包含每一层元素
 * @param {*} root 
 */
function levelOrder(root) {
  let queue = []; //
  let result = [];
  queue.push(root);
  while (queue.length > 0) {
    let size = queue.length; // 当前层级的个数
    let levelArr = [];
    for (let i = 0; i < size; i++) { // 嵌套一层循环，处理每个层级的数据
      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));
/* 结果为：
[
  [ 'F' ],
  [ 'B', 'G' ],
  [ 'A', 'D', 'I' ],
  [ 'C', 'E', 'H' ]
]
*/