二叉树层次遍历打印
时间: 2023-06-30 07:18:21 浏览: 102
二叉树的层次遍历
二叉树的层次遍历可以使用队列来实现。具体步骤如下:
1. 将根节点入队列。
2. 当队列不为空时,循环以下步骤:
1. 取出队列中的节点,打印节点值。
2. 如果该节点有左子节点,则将左子节点加入队列。
3. 如果该节点有右子节点,则将右子节点加入队列。
3. 遍历完所有节点后结束。
下面是示例代码实现:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def level_order_traversal(root: TreeNode):
if not root:
return []
result = []
queue = [root]
while queue:
level = []
size = len(queue)
for i in range(size):
node = queue.pop(0)
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result
```
其中,`root` 是二叉树的根节点,`result` 是保存层次遍历结果的列表,`queue` 是保存节点的队列。
代码中,我们先将根节点加入队列。然后,我们循环处理队列中的节点,首先将该节点的值添加到当前层级的列表 `level` 中,然后将该节点的左右子节点(如果有的话)加入队列。当处理完所有节点后,将当前层级的列表 `level` 添加到结果列表 `result` 中。最终返回结果列表 `result`。
这样,我们就可以使用层次遍历方法打印出二叉树的所有节点了。
阅读全文