二叉树的层次遍历操作
时间: 2023-06-21 21:11:29 浏览: 57
二叉树的层次遍历也称为广度优先遍历,它按照从上到下、从左到右的顺序遍历二叉树的每个节点。具体操作如下:
1. 创建一个空队列,将根节点入队。
2. 当队列不为空时,取出队首节点,访问这个节点,并将其左右子节点(如果存在)依次入队。
3. 重复步骤 2,直到队列为空。
以下是 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 = []
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)
res.append(level)
return res
```
其中,res 为最终结果列表,queue 为队列,size 为当前队列长度,level 为当前层节点值的列表。在每一层遍历结束后,将 level 添加到 res 中,并继续遍历下一层。