[[423982]]

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

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

3

/ \

9 20

/ \

15 7

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

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

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

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

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ù)雜度分析

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

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

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

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

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

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ù)雜度分析：

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