【算法-LeetCode】103. 二叉樹的鋸齒形層序周遊（二叉樹；層序周遊；BFS）

103. 二叉樹的鋸齒形層序周遊 - 力扣（LeetCode）

釋出：2021年9月23日21:19:26

問題描述及示例

給定一個二叉樹，傳回其節點值的鋸齒形層序周遊。（即先從左往右，再從右往左進行下一層周遊，以此類推，層與層之間交替進行）。

給定二叉樹 [3,9,20,null,null,15,7],

  3

 / \

9  20

  /  \

 15   7

傳回鋸齒形層序周遊如下：

[

 [3],

 [20,9],

 [15,7]

]

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

我的題解

我的題解1（BFS層序周遊）

好吧，這道題和我之前做過的層序周遊二叉樹的那道題又是一樣的思路：

參考：【算法-LeetCode】102. 二叉樹的層序周遊（二叉樹；層序周遊；BFS；生成二叉樹）_賴念安的部落格-CSDN部落格

參考：【算法-LeetCode】199. 二叉樹的右視圖（二叉樹；層序周遊；BFS）_賴念安的部落格-CSDN部落格

唯一的差別就是要對樹的深度做一個記錄，若目前層的深度為奇數，則直接把該層周遊所得的節點放入

result

中；若目前層的深度為偶數，則需要把目前層的周遊結果進行翻轉操作之後再放入

result

中。

是以隻需要在上面那道層序周遊題的基礎上做一點點改動就可以了（實際上隻要改動一行代碼就可以了）。有關層序周遊的更多細節描述，可以到上面部落格中回顧，這裡就不再重複了。

本題的相關其他詳解請看下方注釋：

/**
 * 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[]}
 */
var levelOrder = function (root) {
  // 如果該樹是一顆空樹，那麼直接傳回空結果，
  // 不要漏掉這一步判斷，否則無法通過所有LeetCode測試用例
  if(root === null) {
    return [];
  }
  // result 用于存儲所有層的周遊結果
  let result = [];
  // 【tag1】增添了depth用于記錄目前層的深度（這裡是與之前那道單純層序周遊題的差別所在）
  let depth = 0;
  // 初始化queue為輔助隊列，通過數組的push和shift方法的配合，可以實作隊列先進先出的特點
  // 并先把根節點放入隊列，否則後續的while循環将無法工作
  let queue = [root];
  // 如果隊列不為空，則說明還沒有周遊完所有層，注意這個while循環是以層為機關疊代的
  while (queue.length) {
  	// level用于存儲目前層的所有節點，是以每新進一層時都應該将其初始化為空數組
    let level = [];
    // 這個for循環用于周遊目前層的所有節點，注意下面我為什麼不直接寫成 i<queue.length
    for (let i = 0, len = queue.length; i < len; i++) {
      // 彈出隊首節點，但注意不要馬上丢棄它，因為後面還用得上
      let node = queue.shift();
      // 将剛才彈出的節點值存入level
      level.push(node.val);
      // 下面兩個if用于判斷當剛才彈出的節點的左（右）子節點不為空時，則将子節點加入隊尾
      if (node.left) {
        queue.push(node.left);
      }
      if (node.right) {
        queue.push(node.right);
      }
    }
    // for循環結束則說明目前層的節點已經全部存入level中，已經獲得了一個結果
    // 【tag2】這裡是與單純層序周遊的差別點，注意對比
    depth % 2 ? result.push(level) : result.push(level.reverse());
  }
  // while循環結束說明樹中的所有層都已經周遊完，将結果傳回
  return result;
};

送出記錄
33 / 33 個通過測試用例
狀态：通過
執行用時：76 ms, 在所有 JavaScript 送出中擊敗了58.16%的使用者
記憶體消耗：39.3 MB, 在所有 JavaScript 送出中擊敗了83.68%的使用者
時間：	2021/09/23 21:37	
           

總的來說，就是讓上面的

while

循環負責二叉樹深度方向的周遊，而

for

循環則負責某一層中的廣度方向的周遊。其中利用

queue

這個輔助隊列先進先出的結構特點來確定逐層周遊的效果。

上面程式中辨別的【tag1】和【tag2】兩處就是與之前那道層序周遊題的唯一的不同點，注意對比。

官方題解

更新：2021年7月29日18:43:21

因為我考慮到著作權歸屬問題，是以【官方題解】部分我不再粘貼具體的代碼了，可到下方的連結中檢視。

更新：2021年9月23日21:42:01

參考：二叉樹的鋸齒形層序周遊 - 二叉樹的鋸齒形層序周遊 - 力扣（LeetCode）

【更新結束】

有關參考

更新：2021年9月22日22:00:41

參考：【算法-LeetCode】102. 二叉樹的層序周遊（二叉樹；層序周遊；BFS；生成二叉樹）_賴念安的部落格-CSDN部落格

更新：2021年9月23日21:31:44

參考：【算法-LeetCode】199. 二叉樹的右視圖（二叉樹；層序周遊；BFS）_賴念安的部落格-CSDN部落格

更新：2021年7月30日21:03:06

參考：【微信公衆号：代碼随想錄 2020-09-25】二叉樹：層序周遊登場！

參考：深度優先周遊(DFS)和廣度優先周遊(BFS)_JeansPocket的部落格-CSDN部落格_廣度優先周遊

參考：js二維數組定義和初始化的三種方法總結_javascript技巧_腳本之家