如何实现二叉树的层次遍历?
时间: 2023-12-01 09:41:38 浏览: 35
以下是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: TreeNode) -> List[List[int]]:
if not root:
return []
res = []
queue = [root]
while queue:
level = []
for i in range(len(queue)):
node = queue.pop(0)
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(level)
return res
```
上述代码中,我们定义了一个`TreeNode`类来表示二叉树的节点,其中包含节点的值`val`、左子节点`left`和右子节点`right`。`levelOrder`函数接收一个二叉树的根节点作为参数,返回一个列表,其中包含了二叉树的层次遍历结果。
在函数内部,我们首先判断根节点是否为空,如果为空则直接返回空列表。然后定义一个`res`列表来存储遍历结果,定义一个`queue`队列来辅助遍历。将根节点加入队列中,然后开始循环,每次循环都遍历当前队列中的所有节点,将它们的值加入到`level`列表中,并将它们的左右子节点加入到队列中。遍历完当前层的所有节点后,将`level`列表加入到`res`列表中。最后返回`res`列表即可。