【leecode 劍指offer】從上到下列印二叉樹

從上到下列印二叉樹

題目

從上到下列印出二叉樹的每個節點，同一層的節點按照從左到右的順序列印。

示例

例如:

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

傳回

[3,9,20,15,7]

思路

BFS

層序周遊需要使用一個隊列來存儲有用的節點。整體的思路如下：

子節點順序：自左向右

1. 将 root 放入隊首
2. 取出隊首元素，将 val 放入傳回的數組中
3. 檢查隊首元素的子節點，若不為空，則将子節點放入隊列
4. 檢查隊列是否為空，為空，結束并傳回數組；不為空，回到第二步

代碼實作

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var levelOrder = function(root) {
    // 當二叉樹為空時傳回空數組
    if(!root){
        return [];
    }
    // 存儲資料
    var res = [];
    // 輔助隊列，用于記錄周遊的層數  BFS
    var queue = [root];
    // 當輔助隊列不為空時
    while(queue.length){
        // 移除隊首元素
        let first = queue.shift();//傳回值為移除的元素
        // 将元素的值插入結果隊列中
        res.push(first.val);
        // 左元素不為空，加入隊列
        if(first.left){
            queue.push(first.left);
        }
        // 右元素不為空，加入隊列
        if(first.right){
            queue.push(first.right);
        }
    }
    // 傳回結果隊列
    return res;
};
           

總結

這個題目主要考察的是二叉樹的按層周遊，按層周遊的關鍵在于記錄周遊的層數，而我使用的是一個輔助隊列去幫助記錄，對二叉樹進行廣度周遊。