1.题目

这道题是2024-2-15的签到题，题目难度为中等。

考察的知识点为BFS算法（树的层序遍历）

题目链接：二叉树的层序遍历II

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

2.思路

这道题和昨天的层序遍历思路其实差不多，只不过这次需要我们返回从底向上的层序遍历结果。因此我们遍历的算法还是使用BFS算法，只不过这次我们需要改变添加结果的位置。如果是从上往下的层序遍历结果，我们直接用list内置方法append添加到右侧；而如果是从下往上的层序遍历，我们则可以使用list的另外一个内置方法insert来指定插入的位置。

3.代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:# 如果root结点为空if not root:return []# 定义结果列表rst = []# 定义结点队列q = [root]# 如果结点队列不为空while len(q) > 0:# 定义临时队列，用于保存下一层结点队列tmp = []# 定义临时列表，用于保存这一层结点的值r = []# 遍历这一层的结点for n in q:# 添加当前结点的值r.append(n.val)# 如果左子结点存在if n.left:tmp.append(n.left)# 如果右子结点存在if n.right:tmp.append(n.right)# 使用insert方法在列表的左侧插入这一层的结点值rst.insert(0,r)# 更新队列为下一层的结点队列q = tmp# 返回结果return rst