利用队列,编写实现二叉树的层序遍历的代码
时间: 2023-04-24 18:04:40 浏览: 131
算法之二叉树的层序遍历(利用队列实现,需熟练手写)
5星 · 资源好评率100%
二叉树的层序遍历可以利用队列来实现。具体步骤如下:
1. 首先将根节点入队。
2. 然后进入循环,直到队列为空。
3. 在循环中,首先取出队首元素,即当前层的第一个节点。
4. 然后将当前节点的左右子节点依次入队。
5. 将当前节点的值存入结果列表中。
6. 重复步骤3-5,直到队列为空。
下面是实现二叉树层序遍历的代码:
```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 []
queue = [root]
res = []
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是二叉树节点的定义,levelOrder是实现层序遍历的函数。函数的参数是二叉树的根节点,返回值是一个列表,其中每个元素是一层节点的值。在函数内部,首先判断根节点是否为空,如果为空则直接返回空列表。然后创建一个队列,将根节点入队。接着进入循环,直到队列为空。在循环中,首先创建一个空列表level,用于存储当前层的节点值。然后遍历当前层的所有节点,依次取出队首元素,将其值存入level中,并将其左右子节点入队。最后将level存入结果列表res中。重复以上步骤,直到队列为空。最后返回结果列表res即可。
阅读全文