二叉树层序遍历python实现
时间: 2023-10-22 13:10:41 浏览: 54
以下是二叉树层序遍历的Python实现:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def levelOrder(root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
# 如果根节点为空,则返回空列表
if not root:
return []
# 初始化结果列表和队列,将根节点加入队列中
result = []
queue = [root]
# 循环遍历队列,直到队列为空
while queue:
# 获取当前队列的长度,即当前层的节点个数
level_len = len(queue)
level_vals = []
# 遍历当前层的所有节点
for i in range(level_len):
# 弹出队列中的节点,并将其值添加到当前层的值列表中
node = queue.pop(0)
level_vals.append(node.val)
# 如果当前节点有左子节点,则将其加入队列中
if node.left:
queue.append(node.left)
# 如果当前节点有右子节点,则将其加入队列中
if node.right:
queue.append(node.right)
# 将当前层的值列表添加到结果列表中
result.append(level_vals)
# 返回结果列表
return result
```
在上述实现中,我们使用了一个队列来存储遍历过程中的节点。我们首先将根节点加入队列中,然后循环遍历队列,每次弹出队列中的一个节点,并将其左右子节点加入队列中。我们还需要记录当前层的节点个数,以便在遍历完当前层时,能够开始遍历下一层。在遍历完所有层后,我们将所有层的值列表添加到结果列表中,最终返回结果列表。