难度: Medium
给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[[15,7],[9,20],[3]]
示例 2：
输入：root = [1] 输出：[[1]]
示例 3：
输入：root = [] 输出：[]
提示：
- 树中节点数目在范围
[0, 2000]内 -1000 <= Node.val <= 1000
Submission
运行时间: 44 ms
内存: 15.1 MB
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
from collections import deque
class Solution:
def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
if root is None:
return []
q = deque()
q.append(root)
res = []
while q:
floor = []
size = len(q)
for _ in range(size):
node = q.popleft()
floor.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
res.append(floor)
return res[::-1]
Explain
该题解使用 BFS (广度优先搜索) 的思想，通过队列实现。首先将根节点入队，然后逐层遍历二叉树。对于每一层，先统计队列中的节点数(即当前层的节点数)，然后将这些节点依次出队并将它们的值记录在当前层的列表中，同时将它们的非空子节点加入队列，继续下一轮迭代。由于题目要求自底向上输出结果，所以在 BFS 过程中，我们需要把每一层的结果添加到结果列表的头部。最后返回结果列表即可。
时间复杂度: O(n)
空间复杂度: O(n)
from collections import deque
class Solution:
def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
if root is None:
return []
q = deque() # 初始化队列
q.append(root) # 根节点入队
res = [] # 存储最终结果
while q:
floor = [] # 存储当前层的节点值
size = len(q) # 当前层的节点数
# 遍历当前层的所有节点
for _ in range(size):
node = q.popleft() # 当前节点出队
floor.append(node.val) # 记录当前节点的值
# 将当前节点的非空子节点加入队列
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
res.append(floor) # 将当前层的节点值列表添加到结果列表的头部
return res[::-1] # 反转结果列表，实现自底向上的输出
Explore
在BFS层序遍历的过程中，只有非空的子节点才会被加入到队列中。在代码里，每次从队列中取出一个节点后，会检查这个节点的左右子节点是否存在（即不为null）。只有当子节点非空时（`if node.left:` 和 `if node.right:`），这些子节点才会被添加到队列中。这样，队列中永远不会包含null值，只包含实际存在的TreeNode对象。
使用`res.append(floor)`后再通过`res[::-1]`返回结果的方式比直接使用`res.insert(0, floor)`更为高效。这是因为列表的`append`操作是O(1)的，即在列表的末尾添加元素的时间复杂度是常数。而`insert(0, floor)`操作是O(n)的，因为它需要在列表的开始位置插入元素，这会导致已有元素都要向后移动一位。因此，虽然两种方法都能实现自底向上的层序遍历，但前者在性能上更优，特别是在处理大数据时差异更为明显。
BFS层序遍历确实保证了每个节点都会被访问一次，并且这个特性适用于所有类型的二叉树，包括完全二叉树、不完全二叉树、倾斜二叉树等。没有例外情况，因为BFS的遍历逻辑是从根节点开始，逐层向下，每次都从队列中取出当前层的所有节点，同时将它们的子节点加入队列以便下一层的遍历。这种方法确保了每个节点都被精确地访问一次，不会遗漏也不会重复访问。