利用一个队列,实现对一颗二叉树的层序遍历 的代码
时间: 2023-11-20 07:05:58 浏览: 93
算法之二叉树的层序遍历(利用队列实现,需熟练手写)
5星 · 资源好评率100%
好的,下面是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 _ 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`函数来进行层序遍历。在函数中,我们首先判断根节点是否为空,如果为空,则直接返回空列表。否则,我们定义一个队列`queue`,将根节点入队,然后开始循环。在循环中,我们每次取出队首元素,输出它的值,并将其左右子节点(如果存在的话)依次入队。这样就完成了一层的遍历。我们不断重复这个过程,直到遍历完整棵树。最后将每一层的节点值保存到列表`res`中,并返回即可。
希望能够帮到你!
阅读全文