给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。
时间: 2024-12-16 16:23:28 浏览: 2
层序遍历是一种常见的二叉树遍历方法,它按照从上到下、从左到右的顺序逐层访问节点。对于给定的二叉树根节点 `root`,你可以通过队列(先进先出)来实现这个过程:
1. 创建一个空的队列,并将根节点入队。
2. 当队列非空时,循环执行以下步骤:
a. 弹出队首元素作为当前节点。
b. 访问当前节点的值(如果需要的话)。
c. 将当前节点的左右子节点(如果存在)分别入队。
3. 执行完上述循环后,所有节点都已按照层序遍历的方式访问过。
这是一个典型的深度优先搜索(DFS)与广度优先搜索(BFS)混合的应用,其中队列用于维护每一层的节点。
如果你正在寻找实际的代码实现,这里是一个Python示例:
```python
from collections import deque
def levelOrder(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
current_level = [node.val for node in iter(queue.popleft, None) for _ in range(level_size)]
result.append(current_level)
# 添加下一层节点
for _ in range(level_size):
if queue and queue[0].left:
queue.append(queue[0].left)
if queue and queue[0].right:
queue.append(queue[0].right)
return result
```
阅读全文