作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
题目描述
给你一个二叉树，请你返回其按层序遍历得到的节点值。 （即逐层地，从左到右访问所有节点）。
示例
示例
输入：
3 / \ 9 20 / \ 15 7
输出：
[ [3], [9,20], [15,7] ]
方法一：迭代使用队列
解题步骤
- 初始化：使用一个队列来存储每一层的节点。
- 迭代处理：每次迭代开始时，记录当前队列的长度，这代表了当前层的节点数；然后从队列中逐个取出节点，将其值加入当前层的结果列表，并将其子节点加入队列以用于下一次迭代。
Python 示例
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def levelOrder(root): """ 使用队列实现二叉树的层序遍历 :param root: TreeNode, 二叉树的根节点 :return: List[List[int]], 层序遍历的结果 """ if not root: return [] result, queue = [], [root] while queue: level_size = len(queue) current_level = [] for _ in range(level_size): node = queue.pop(0) current_level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(current_level) return result
算法分析
- 时间复杂度：(O(n))，每个节点被访问一次。
- 空间复杂度：(O(n))，队列中最多同时存储两层节点。
算法改进
尽管迭代使用队列的方法对于层序遍历非常直观和高效，但它也有一些潜在的问题和限制。
1. 空间复杂度
- 问题：在最坏的情况下（例如完全二叉树），队列可能需要存储树中所有的叶子节点，这大约是节点总数的一半，因此空间复杂度可以达到 (O(n))。
- 改进：虽然对于层序遍历来说，这种空间需求通常是不可避免的，但可以通过优化数据结构的选择或者在特定情况下采用不同的遍历策略来减轻空间压力。
2. 效率问题
- 问题：在 Python 中，使用列表作为队列并进行频繁的
pop(0)操作是低效的，因为这是一个 (O(n)) 的操作。 - 改进：可以使用
collections.deque，它支持 (O(1)) 时间复杂度的 append 和 popleft 操作，这样可以显著提高效率。
3. 并发处理
- 问题：当前的队列方法是单线程的，对于非常大的树，这可能导致性能瓶颈。
- 改进：可以考虑使用并行或并发技术来处理不同的树层。例如，可以在多线程环境中为每一层的遍历分配一个线程，但这需要处理线程同步的问题，确保层序的顺序性。
Python 示例代码改进
以下是考虑了上述改进后的 Python 示例代码：
from collections import deque class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def levelOrder(root): """ 使用 deque 实现二叉树的层序遍历 :param root: TreeNode, 二叉树的根节点 :return: List[List[int]], 层序遍历的结果 """ if not root: return [] result = [] queue = deque([root]) while queue: level_size = len(queue) current_level = [] for _ in range(level_size): node = queue.popleft() # 使用 deque 提高出队效率 current_level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(current_level) return result
在这个改进版本中，我使用了 collections.deque 来优化队列操作，这样 popleft() 和 append() 都是 (O(1)) 的操作，有效提高了遍历的效率。
通过这些改进，可以解决一些原始方法中存在的效率和性能问题，使得层序遍历更加高效和适应更多复杂的应用场景。
方法二：递归
解题步骤
- 定义递归函数：使用一个辅助函数来处理每一层的节点。函数接收当前的节点和节点的层级作为参数。
- 递归逻辑：将节点的值添加到其对应层级的列表中。递归地处理左子节点和右子节点，层级参数加一。
Python 示例
def levelOrder(root): """ 递归实现二叉树的层序遍历 :param root: TreeNode :return: List[List[int]] """ def helper(node, level): if not node: return if len(result) == level: result.append([]) result[level].append(node.val) helper(node.left, level + 1) helper(node.right, level + 1) result = [] helper(root, 0) return result
算法分析
- 时间复杂度：(O(n))，每个节点访问一次。
- 空间复杂度：(O(h))，递归栈的深度，其中 (h) 是树的高度。
不同算法的优劣势对比
| 特征 | 方法一：迭代队列 | 方法二：递归 |
| 时间复杂度 | (O(n)) | (O(n)) |
| 空间复杂度 | (O(n)) | (O(h)) |
| 优势 | 直接且实用 | 简洁明了 |
| 劣势 | 空间开销大 | 依赖栈深度 |
应用示例
层序遍历在许多场景中都非常有用，比如在图形界面中显示树结构、在网络服务中以层序格式发送数据结构、以及在 AI 和机器学习中构建决策树时评估节点。
欢迎关注微信公众号 数据分析螺丝钉
