[[423982]]

給定一個二叉樹，返回其節(jié)點值自底向上的層次遍歷。(即按從葉子節(jié)點所在層到根節(jié)點所在的層，逐層從左向右遍歷)

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

3

/ \

9 20

/ \

15 7

返回其自底向上的層次遍歷為：

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

解法一：BFS(廣度優(yōu)先遍歷)

BFS 是按層層推進的方式，遍歷每一層的節(jié)點。題目要求的是返回每一層的節(jié)點值，所以這題用 BFS 來做非常合適。BFS 需要用隊列作為輔助結(jié)構(gòu)，我們先將根節(jié)點放到隊列中，然后不斷遍歷隊列。

const levelOrderBottom = function(root) { 
    if(!root) return [] 
    let res = [],  
        queue = [root] 
    while(queue.length) { 
        let curr = [], 
            temp = [] 
        while(queue.length) { 
            let node = queue.shift() 
            curr.push(node.val) 
            if(node.left) temp.push(node.left) 
            if(node.right) temp.push(node.right) 
        } 
        res.push(curr) 
        queue = temp 
    } 
    return res.reverse() 
}; 

復(fù)雜度分析

• 時間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(n)

解法二：DFS(深度優(yōu)先遍歷)

DFS 是沿著樹的深度遍歷樹的節(jié)點，盡可能深地搜索樹的分支

DFS 做本題的主要問題是：DFS 不是按照層次遍歷的。為了讓遞歸的過程中同一層的節(jié)點放到同一個列表中，在遞歸時要記錄每個節(jié)點的深度 depth 。遞歸到新節(jié)點要把該節(jié)點放入 depth 對應(yīng)列表的末尾。

當遍歷到一個新的深度 depth ，而最終結(jié)果 res 中還沒有創(chuàng)建 depth 對應(yīng)的列表時，應(yīng)該在 res 中新建一個列表用來保存該 depth 的所有節(jié)點。

const levelOrderBottom = function(root) { 
    const res = [] 
    var dep = function (node, depth){ 
        if(!node) return 
        res[depth] = res[depth]||[] 
        res[depth].push(node.val) 
        dep(node.left, depth + 1) 
        dep(node.right, depth + 1) 
    } 
    dep(root, 0) 
    return res.reverse()    
}; 

復(fù)雜度分析：

• 時間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(h)，h為樹的高度