102. Binary Tree Level Order Traversal

今天一樣延續著「二元樹（Binary Tree）」的題目，其實樹相關的議題可以算是面試時的熱門考題，不同的情境可以玩轉資料結構與演算法兩種方向。常見的遍歷方法有依據 Root 被找到的先後做排序的「前序」、「中序」跟「後序」，但一題考的是以階層（深度）為順序的「Level Order Traversal」。

先看一下題目描述

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

再搭配範例理解題目

• Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

階層（Level）在樹當中代表的是深度，從最上層的 Root 開始依序往下層增加。根據不同的定義可能會從 Level = 0 或 Level = 1 開始計數，但這一題不影響。而這個要求用階層為單位，將同一層的點放在同一個容器、依序將不同層的容器再放在一個大的容器內回傳。

開始實作

在理解完題目與條件之後，那我們下一步就開始「#初探直覺解」並且一起嘗試「#刻意優化」的過程：

方法 ①：自定義儲存格式

這個題目比較麻煩的地方在於要如何找出每一個點分別在哪一層當中，因此第一個想法是可以利用 map 自定義儲存格式，將點與所在階層記錄下來：

waitlist = [ 
    { 'level': 0, 'node': root}
]

首先，將每一個紀錄中的根據階層儲存到最終的結果中：

while len(waitlist) > 0:
    cur = waitlist.pop()
    node = cur['node']
    
    res[cur['level']].append(node.val)

同時也需要將每一個點下一層的左右兩點記錄下來：

while len(waitlist) > 0:
    cur = waitlist.pop()
    node = cur['node']
    waitlist.append({'level': cur['level']+1, 'node':node.right});
    waitlist.append({'level': cur['level']+1, 'node':node.left});

用 Python 實作一次

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:  return []

        res = {};
        waitlist = [ { 'level': 0, 'node': root} ]

        while len(waitlist) > 0:
            cur = waitlist.pop()
            node = cur['node']
            
            res.setdefault(cur['level'], [])
            res[cur['level']].append(node.val)

            if node.right:
                waitlist.append({'level':cur['level']+1, 'node':node.right});
            if node.left:
                waitlist.append({'level':cur['level']+1, 'node':node.left});

        return [res[i] for i in res]

也可以用 JavaScript 復刻一次

var levelOrder = function(root) {
    if (!root)  return [];

    var res = {};
    var waitlist = [ { level:0, node:root} ];

    while(waitlist.length > 0){
        var cur = waitlist.pop();
        var node = cur.node;
        
        if(!res[cur.level]) res[cur.level] = [];
        res[cur.level].push(node.val);
        
        if(node.right) waitlist.push({level:cur.level+1, node:node.right});
        if(node.left) waitlist.push({level:cur.level+1, node:node.left});
    }
    
    var result = [];
    for(var i in res){
        result.push(d[i]);
    }

    return result;
};

方法 ②：用 Stack 暫存資料

第二種方法可以利用 Stack 的特性來記憶不同階層的資料，而不用自訂義的格式來記錄。這種方法將 Stack 作為所有需要跑過一輪的點，然後再利用 currents 存放該層的點、childs 存放下一層的點。每跑過一輪時，將 currents 合併回結果，將 childs 寫入 stack 作為下一輪需要考慮的點。

用 Python 實作一次

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root: return []
        res, stack = [], [[root]]

        while stack:
            nodes = stack.pop()
            currents = []
            childs = []
            for node in nodes:
                currents.append(node.val)
                if node.left: childs.append(node.left)
                if node.right: childs.append(node.right)
            
            res.append(currents)
            if childs: stack.append(childs)
                
        return res

也可以用 JavaScript 復刻一次

const levelOrder = function(root) {
    if (!root)  return [];
    let res = [], stack = [[root]];
    
    while (stack.length > 0) {
        nodes = stack.pop()
        currents = []
        childs = []
        for(let node of nodes){
            currents.push(node.val)
            if(node.left) childs.push(node.left)
            if(node.right) childs.push(node.right)
        }
        res.push(currents)
        if(childs.length > 0) stack.push(childs)
    }
    return res;
};

方法 ③：用 Queue 暫存資料

在 Stack 中方法中需要利用兩層的 [[...]] 用來儲存上下層的資料，才能區分先後的關係。但如果我們改用 Queue 的結構，因為其先進先出（FIFO）的特性，只需要改成 [...] 一層來存放即可：

用 Python 實作一次

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:  return []
        res, queue = [], [root]

        while queue:
            levelQueue = []
            for _ in range(len(queue)):
                node = queue.pop(0)
                levelQueue.append(node.val)
                if node.left: queue.append(node.left)
                if node.right: queue.append(node.right)   
            res.append(levelQueue)
        
        return res

也可以用 JavaScript 復刻一次

const levelOrder = function(root) {
    if (!root)  return [];
    let res = [], queue = [root];
    
    while (queue.length > 0) {
        let levelQueue = [];
        let length = queue.length;
        for(let i = 0; i < length; i++){
            const node = queue.shift(); 
            levelQueue.push(node.val)
            if(node.left !== null) queue.push(node.left);
            if(node.right !== null) queue.push(node.right);
        }
        res.push(levelQueue)
    }
    return res;
};

反思沉澱

遍歷是樹（Tree）特性的一種延伸操作，不同於線性的搜尋，因為每一個節點可能會有左/右分支，因此有不同的先後順序找法。這個題目可以搭配「自定義的格式」或直接利用「Stack」與「Queue」之類的抽象資料結構特性來保存資料間的順序來實現題目要求。

舉一反三看看相似題

最後可以從題目提供的相似題看一下有哪些類似的題目，適合作為你下一個嘗試的練習：

• 107. Binary Tree Level Order Traversal II
• 111. Minimum Depth of Binary Tree
• 637. Average of Levels in Binary Tree
• 429. N-ary Tree Level Order Traversal

嗨，大家好！我是維元，一名擅長網站開發與資料科學的雙棲工程師，斜槓於程式社群【JSDC】核心成員及【資料科學家的工作日常】粉專經營。目前在 ALPHACamp 擔任資料工程師，同時也在中華電信、工研院與多所學校等單位持續開課。擁有多次大型技術會議講者與競賽獲獎經驗，持續在不同的平台發表對 #資料科學、 #網頁開發 或 #軟體職涯 相關的分享，邀請你加入 訂閱 接收最新資訊。