企业官网建设流程全解析

LeetCode 107. 二叉树的层序遍历 II Python3 实现

思路

题目要求自底向上的层序遍历，即从叶子层到根层逐层返回。

最简单做法：先用普通的 BFS（队列）自顶向下收集每一层，最后把结果整体反转。

Python3 代码

fromcollectionsimportdequefromtypingimportList,Optional# 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 = rightclassSolution:deflevelOrderBottom(self,root:Optional[TreeNode])->List[List[int]]:ifnotroot:return[]res=[]q=deque([root])whileq:level=[]# 当前层的节点数for_inrange(len(q)):node=q.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:returnifdepth==len(res):res.append([])res[depth].append(node.val)dfs(node.left,depth+1)dfs(node.right,depth+1)dfs(root,0)returnres[::-1]

DFS 也是 O(n) 时间，但递归深度可能达到树高，最坏 O(n)。实际刷题时 BFS 更直观。