二叉树的层次遍历II

题目链接

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

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

   3
  /  \
9   20
      /   \
  15    7
返回其自底向上的层次遍历为:

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

解题方法

DFS

看到题目首先想到的肯定是直接BFS,再将结果列表倒转即可,但是DFS方法其实也简洁方便。

只是,我们在做DFS时需要记录当前遍历的层次是第几层,并将该层节点的值都插入对应数据结构中。

这里使用python collections中的OrderedDict,该有序字典可以保持插入顺序。因此,在DFS之后,我们仍可以遍历字典并倒序。计算流程如下:

算法流程图算法流程图

我们复习一下二叉树的DFS遍历框架:

def dfs(node):
    #终止条件,结点为空
    if not node:
        return
    #对当前结点进行记录
    path.append(node)
    dfs(node.left)
    dfs(node.right)

那么,本题的解法就非常简单了,代码如下,可复制到leetcode运行:

import collections
class Solution:
    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        def dfs(node:TreeNode,layer_index):
            #终止条件
            if not node:
                return  
            #先序遍历
            if layer_index not in result_dict:
                result_dict[layer_index]=[]
            result_dict[layer_index].append(node.val)
            dfs(node.left,layer_index+1)
            dfs(node.right,layer_index+1)
        
        result_dict=collections.OrderedDict()
        dfs(root,0)
        return [l for l in reversed([v for i,v in result_dict.items()])]

BFS

DFS的缺点需要熟悉OrderDict的使用,造成空间复杂度大。BFS就更适合本问题,每次遍历一层的所有结点,并插入该层的列表中即可。

那么我们也回顾下二叉树BFS的框架。

#将根节点入队列
queue=collections.deque([root])
def bfs():
    #当队列为空时,bfs结束
    while queue:
        #保存每层状态
        level=[]
        #该层结点数
        size=queue.size()
        for _ in range(size):
            #出队列
            cur_node=queue.popleft()
            #保存该结点信息
            level.append(cur_node.val)
            #将该结点的下一层结点,即子节点入队列
            if cur_node.left:
                queue.append(cur_node.left)
            if cur_node.right:
                queue.append(cur_node.right)
        #该层遍历结束,保存该层信息
        result.append(level)

有了BFS框架,本题基本上就已经解决了,代码如下:

import collections
class Solution:
    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        result_list=list()
        if not root:
            return result_list
        #定义一个队列,存储每一层的节点
        queue=collections.deque([root])
        def bfs():
            while queue:
                level=[]
                size = len(queue)
                for _ in range(size):
                    cur_node=queue.popleft()
                    level.append(cur_node.val)
                    if cur_node.left!=None:
                        queue.append(cur_node.left)
                    if cur_node.right!=None:
                        queue.append(cur_node.right)
                #该层遍历完
                result_list.append(level)
        bfs()
        return [l for l in reversed(result_list)]