内容摘要：给定一个二叉树，返回其节点值自底向上的层次遍历。(即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历)例如：给定二叉树 [3,9,20,null,null,15,7] ,3/ \9 20/ \15

给定一个二叉树，每日返回其节点值自底向上的算法层次遍历。(即按从叶子节点所在层到根节点所在的叉树次遍层，逐层从左向右遍历)

例如：给定二叉树 [3,每日9,20,null,null,15,7] ,

3

/ \

9 20

/ \

15 7

返回其自底向上的层次遍历为：

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

解法一：BFS(广度优先遍历)

BFS 是按层层推进的方式，遍历每一层的算法节点。题目要求的叉树次遍是返回每一层的节点值，所以这题用 BFS 来做非常合适。网站模板每日BFS 需要用队列作为辅助结构，算法我们先将根节点放到队列中，叉树次遍然后不断遍历队列。每日

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() }; 

复杂度分析

时间复杂度：O(n) 空间复杂度：O(n)

解法二：DFS(深度优先遍历)

DFS 是沿着树的深度遍历树的节点，尽可能深地搜索树的叉树次遍分支

DFS 做本题的主要问题是：DFS 不是按照层次遍历的。为了让递归的每日过程中同一层的云服务器节点放到同一个列表中，在递归时要记录每个节点的算法深度 depth 。递归到新节点要把该节点放入 depth 对应列表的叉树次遍末尾。

当遍历到一个新的深度 depth ，而最终结果 res 中还没有创建 depth 对应的列表时，应该在 res 中新建一个列表用来保存该 depth 的所有节点。

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()    }; 

复杂度分析：

时间复杂度：O(n) 空间复杂度：O(h)，h为树的高度