107. 二叉树的层序遍历 II(中)

• 题目
• 题解：BFS

题目

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

题解：BFS

• 用BFS把每层的结点存在一个单独的列表里，最后翻转整个结果列表

class Solution:
    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:# 如果根节点为空，直接返回空列表
            return []
        res=[]# 存储结果的列表
        q=[]# 使用列表作为队列
        q.append(root)# 将根节点加入队列
        step=1# 记录当前层的编号
        while q:#当队列不为空时
            size=len(q)
            res1=[] # 存储当前层的结果
            
            for _ in range(size):
                cur = q.pop(0)# 从队列头部取出节点
                res1.append(cur.val)# 将当前节点的值加入当前层的结果列表
                if cur.left:# 将左子节点加入队列
                    q.append(cur.left)
                if cur.right:# 将右子节点加入队列
                    q.append(cur.right)
            res.append(res1)   # 将当前层的结果列表加入最终结果列表
            step+=1   # 增加层编号
        res.reverse()   # 反转最终结果列表
        return res