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

構(gòu)造一個(gè)樹的數(shù)據(jù)結(jié)構(gòu)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); // 先保存根節(jié)點(diǎn)
  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); // 中間保存根節(jié)點(diǎn)
  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']

注：上述三種遍歷都是深度優(yōu)先遍歷

廣度優(yōu)先遍歷

/**
 * 廣度優(yōu)先遍歷，返回一維數(shù)組
 * @param {*} root 
 */
var BFS = function (root) {
  let queue = []; //JS數(shù)組實(shí)現(xiàn)隊(duì)列吊履，先進(jìn)先出
  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']

層序遍歷

什么是層序遍歷呢安皱？簡單來說，層序遍歷就是把二叉樹分層艇炎，然后每一層從左到右遍歷：

乍一看來酌伊，這個(gè)遍歷順序和 BFS 是一樣的，我們可以直接用 BFS 得出層序遍歷結(jié)果缀踪。然而居砖，層序遍歷要求的輸入結(jié)果和 BFS 是不同的燕锥。層序遍歷要求我們區(qū)分每一層，也就是返回一個(gè)二維數(shù)組悯蝉。而 BFS 的遍歷結(jié)果是一個(gè)一維數(shù)組，無法區(qū)分每一層托慨。

作者：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）
著作權(quán)歸作者所有鼻由。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)哨查，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處西雀。

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

/**
 * 層序遍歷允坚，返回二維數(shù)組欺矫，包含每一層元素
 * @param {*} root 
 */
function levelOrder(root) {
  let queue = []; //
  let result = [];
  queue.push(root);
  while (queue.length > 0) {
    let size = queue.length; // 當(dāng)前層級(jí)的個(gè)數(shù)
    let levelArr = [];
    for (let i = 0; i < size; i++) { // 嵌套一層循環(huán)嚷掠，處理每個(gè)層級(jí)的數(shù)據(jù)
      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));
/* 結(jié)果為：
[
  [ 'F' ],
  [ 'B', 'G' ],
  [ 'A', 'D', 'I' ],
  [ 'C', 'E', 'H' ]
]
*/