每日算法：二叉树的层次遍历

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

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

3

/ \

9 20

/ \

15 7

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

1. [
2. [15,7],
3. [9,20],
4. [3]
5. ]

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

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

1. constlevelOrderBottom=function(root){
2. if(!root)return[]
3. letres=[],
4. queue=[root]
5. while(queue.length){
6. letcurr=[],
7. temp=[]
8. while(queue.length){
9. letnode=queue.shift()
10. curr.push(node.val)
11. if(node.left)temp.push(node.left)
12. if(node.right)temp.push(node.right)
13. }
14. res.push(curr)
15. queue=temp
16. }
17. returnres.reverse()
18. };

复杂度分析

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

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

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

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

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

1. constlevelOrderBottom=function(root){
2. constres=[]
3. vardep=function(node,depth){
4. if(!node)return
5. res[depth]=res[depth]||[]
6. res[depth].push(node.val)
7. dep(node.left,depth+1)
8. dep(node.right,depth+1)
9. }
10. dep(root,0)
11. returnres.reverse()
12. };

复杂度分析：

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

原文链接：https://mp.weixin.qq.com/s/gfvV_MFbHT9bX_DTobnEbg