Leetcode 算法題解系列 - 二叉樹的層序遍歷詳情 - leetcode,javascript,算法,二叉樹安歌博客

本專題旨在分享刷Leecode過程發現的一些思路有趣或者有價值的題目。【當然是基於js進行解答】。
（這道題應該算是二叉樹的基礎題，建議還是學一下，不難且經典）

題目相關

原題地址: https://leetcode-cn.com/probl...

題目描述:

從上到下按層打印二叉樹，同一層的節點按從左到右的順序打印，每一層打印到一行，例如，給定二叉樹: [3,9,20,null,null,15,7]

返回其層次遍歷結果：

[
  [3],
  [9,20],
  [15,7]
]

Tips

考慮某些同學可能比較少用js來刷leetcode，我們在這裏簡單介紹下,關於樹類型的數據輸入,在js裏的表示。形如上題中的內容，給定二叉樹的輸入，其實並非一個數組，而應該是如下所示: 每個節點是一個object

  const root = {
    val: 3,
    left: { // left表示當前節點的左側子節點
      val: 9,
      left: null, // 對照上圖可以看到 節點9沒有左右子節點
      right: null,
    },
    right: {
      val: 20,
      left: {
        val: 15, // 對照上圖可以看到 節點15沒有左右子節點
        left: null, 
        right: null,
      }, 
      right: {
        val: 7, // 對照上圖可以看到 節點7沒有左右子節點
        left: null, 
        right: null,
      },
    }
  }

思路解析

這道題比較基礎，其實考的是BFS+層序遍歷，怎麼説呢？
劃重點.png

首先 BFS(Breadth First Search)也就是廣度優先搜索, 指的是在遍歷過程，每次總是優先遍歷當前節點的所有鄰接節點，將其放入一個隊列，比如上題的例子：

step1: 首先準備一個空隊列（也就是數組） [ ] ，並且把根節點放入數組中,也就是 [3] ；
step2: 先取出隊列的最前面節點（此時隊列只有節點3，取出之後隊列置空），然後把它的所有鄰接節點（在二叉樹裏面也就是左右子節點）按順序加入訪問隊列，所以此時隊列元素為 [9 20] ,
step3: 繼續按照第二步的規則，取出節點9，並把9的子節點放入隊列（無子節點）；再把節點20取出，並且把節點20的子節點存入隊列，此時隊列剩餘元素為 [15, 7] ;
step4: 繼續按照第二步規則，取出節點15，並把子節點放入隊列（無子節點）；再把節點7取出，並且把節點7的子節點存入隊列，此時隊列剩餘元素為 []，隊列為空結束整個過程 ;

仔細觀察以上的步驟，你發現了嗎？

除了第一步初始化數據，後續的所有步驟都在按照第2步的規則重複；
觀察每一步的取出結果：
1. step2, 取出[3];
2. step3, 取出[9, 20];
3. step4, 取出[15, 17];
這裏每一步的取出結果正好就是題設要求的每一層遍歷的結果。
整個過程結束條件，就是節點隊列為空。
這道題講到這裏，其實大致思路就已經很清晰了，或者説，其實上面的步驟就已經是偽代碼了(沒辦法，因為題目本身就非常典型-_-!)

首先第2步的規則肯定就是主函數，因為它全程一直循環；
其次，初始條件/結束條件分別對應的是 根節點入隊列，和隊列為空；
唯一的難點，在於如何優雅地處理【分層輸出】，而這一點我建議大家直接看我最後貼地完整代碼。

完整代碼

那麼其實就可以直接看代碼了:

var levelOrder = function(root) {
    if (!root) { // 如果根節點都不存在 那直接結束 
        return [];
    }

    const nodes = [root]; // 初始化，對應前面分析裏地初始條件，
    const res = []; 

    while(nodes.length > 0) { // 外層循環 當節點隊列為空時結束
        const tempRes = [];
        let isEmpty = false;

        // 【注意點】這個內循環 也就是處理分層輸出地精髓所在，大家可以仔細揣摩下這個循環條件
        // 嘗試回答這裏為什麼不採用 “i=0 ；i<nodes.length； i++”的形式
        for(let i = nodes.length;i > 0 ; i--) { 
            const node = nodes.shift();
            tempRes.push(node.val);
            if(node.left) {
                nodes.push(node.left);
            }
            if(node.right) {
                nodes.push(node.right);
            }
        }
        res.push(tempRes);
       
    }
    return res;
 };

好了整體的題目算是基礎題，就不畫動態圖了（畫圖很耗時），但是想兩個問題給大家思考：