LeetCode 107. 二叉树的层序遍历 II Python3 实现思路题目要求自底向上的层序遍历即从叶子层到根层逐层返回。最简单做法先用普通的 BFS队列自顶向下收集每一层最后把结果整体反转。Python3 代码fromcollectionsimportdequefromtypingimportList,Optional# Definition for a binary tree node.# class TreeNode:# def __init__(self, val0, leftNone, rightNone):# self.val val# self.left left# self.right rightclassSolution:deflevelOrderBottom(self,root:Optional[TreeNode])-List[List[int]]:ifnotroot:return[]res[]qdeque([root])whileq:level[]# 当前层的节点数for_inrange(len(q)):nodeq.popleft()level.append(node.val)ifnode.left:q.append(node.left)ifnode.right:q.append(node.right)res.append(level)# 自底向上反转结果returnres[::-1]注意deque 的左侧弹出方法是 popleft()不是 pop(0)。拼写为 p-o-p-l-e-f-t即 popleft()。复杂度分析项目 复杂度时间 O(n)每个节点入队出队一次空间 O(n)队列最大宽度 结果数组示例验证输入 3 / \ 9 20 / \ 15 7 BFS 自顶向下[[3], [9, 20], [15, 7]] 反转后 [[15, 7], [9, 20], [3]]另一种写法DFS 递归classSolution:deflevelOrderBottom(self,root:Optional[TreeNode])-List[List[int]]:res[]defdfs(node,depth):ifnotnode:returnifdepthlen(res):res.append([])res[depth].append(node.val)dfs(node.left,depth1)dfs(node.right,depth1)dfs(root,0)returnres[::-1]DFS 也是 O(n) 时间但递归深度可能达到树高最坏 O(n)。实际刷题时 BFS 更直观。
