题目

难度：★☆☆☆☆
类型：二叉树

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

示例

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

    3
   / \
  9  20
    /  \
   15   7

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

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

解答

这里我们使用最简单的数组去实现。通过观察我们发现，结果列表中的每个元素都是列表，而且是按照二叉树的层次逆序进行排列的，我们定义一个结果列表res用于存储最终遍历结果，用列表cur_layer存储每一层的遍历结果。我们用这里用两个队列queue和next_queue分别表示当前层的所有结点和下一层的所有结点。具体流程如下：

1. 初始化结果列表res和当前层结点列表queue；

2. 只要当前层结点列表不为空，则进行循环，每轮循环进行以下操作：
   （1）初始化当前层结果列表cur_layer和下一层结点列表next_queue；
   （2）依次从当前层中取出结点元素，当该结点不为空时，将当前结点的值加入到当前层结果列表cu_layer中，并将该结点的左右孩子结点放在下一层结点列表next_queue中。
   （3）把本层获得的结果列表cur_layer加入到最终结果列表res中，并更新queue为下一层结点列表next_queue。

3. 返回最终结果res。

class Solution:
    def levelOrderBottom(self, root):
        queue = []                                                  # 结果列表
        cur = [root]                                                # 接下来要循环的当前层节点，存的是节点
        while cur:                                                  # 当前层存在结点时
            cur_layer_val = []                                      # 初始化当前层结果列表为空，存的是val
            next_layer_node = []                                    # 初始化下一层结点列表为空
            for node in cur:                                        # 遍历当前层的每一个结点
                if node:                                            # 如果该结点不为空，则进行记录
                    cur_layer_val.append(node.val)                  # 将该结点的值加入当前层结果列表的末尾
                    next_layer_node.extend([node.left, node.right]) # 将该结点的左右孩子结点加入到下一层结点列表
            if cur_layer_val:                                       # 只要当前层结果列表不为空
                queue.insert(0, cur_layer_val)                      # 则把当前层结果列表插入到队列首端
            cur = next_layer_node                                   # 下一层的结点变成当前层，接着循环
        return queue                                                # 返回结果队列

如有疑问或建议，欢迎评论区留言~