题目： 145. 二叉树的层序遍历
Python
1. 层序遍历模板
from collections import deque def levelOrderTraverse(root): if root is None: return q = deque() q.append(root) # 记录当前遍历到的层数（根节点视为第一层） depth = 1 while q: # 需要知道“这一层什么时候结束”，所以用 sz 锁定当前层的节点个数，实现分层控制。 sz = len(q) for i in range(sz): cur = q.popleft() # 访问 cur 节点，同时知道它所在的层数 print(f"depth = {depth}, val = {cur.val}") # 把 cur 的左右子节点加入队列 if cur.left is not None: q.append(cur.left) if cur.right is not None: q.append(cur.right) depth += 1
但问题是，这道题有输出的要求。真就是变一点点就不会做了。
2. 正确答案
照着题解 https://leetcode.cn/problems/binary-tree-level-order-traversal/solutions/2361604/102-er-cha-shu-de-ceng-xu-bian-li-yan-du-dyf7/ 抄的。
# 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 levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:if root is None:return []res, queue = [], collections.deque()queue.append(root)while queue:tmp = []for _ in range(len(queue)):node = queue.popleft()tmp.append(node.val)if node.left is not None:queue.append(node.left)if node.right is not None:queue.append(node.right)res.append(tmp)return res
复杂度分析
- 时间复杂度 \(O(N)\)： \(N\) 为二叉树的节点数量，即 BFS 需循环 \(N\) 次。
- 空间复杂度 \(O(N)\)： 最差情况下，即当树为平衡二叉树时，最多有 \(N/2\) 个树节点同时在 queue 中，使用 \(O(N)\) 大小的额外空间。