利用一个队列,实现对一颗二叉树的层序遍历
时间: 2023-12-01 11:17:57 浏览: 35
利用一个队列,可以很容易地实现对一颗二叉树的层序遍历。具体思路如下:
1. 将根节点入队。
2. 当队列不为空时,依次取出队列中的节点,并将其左右子节点入队。
3. 对于每个出队的节点,输出其值。
4. 重复步骤2和3,直到队列为空。
以下是一个示例代码(假设二叉树的节点结构为Node):
```python
def level_order_traversal(root):
if root is None:
return []
queue = [root]
res = []
while queue:
level_size = len(queue)
level_node_vals = []
for i in range(level_size):
node = queue.pop(0)
level_node_vals.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(level_node_vals)
return res
```
在这个函数中,首先判断根节点是否为空。然后创建一个队列,并将根节点入队。接下来,进入一个循环,循环条件为队列不为空。在循环中,先记录当前层的节点数(即队列的长度),然后创建一个列表用于存储当前层的节点值。接着,依次取出队列中的节点,并将其左右子节点入队。同时,将取出的节点的值存储到当前层的节点值列表中。当当前层的所有节点都处理完后,将该层的节点值列表存储到结果列表中。最后,重复以上步骤直到队列为空。