二叉树的层次遍历
时间: 2023-06-22 20:26:55 浏览: 105
二叉树的层次遍历可以用广度优先搜索(BFS)实现。BFS 是一种从根节点开始逐层扫描整棵树的算法,可以按照层次顺序遍历二叉树。
具体实现步骤如下:
1. 创建一个队列,将根节点入队。
2. 当队列不为空时,依次从队列中取出节点,并将其左右子节点加入队列。
3. 记录当前遍历的层数,将同一层的节点存储在一个列表中。
4. 遍历完一层后,将该层节点的值存储在结果列表中,并清空该层节点列表。
5. 重复上述过程,直到队列为空。
以下是 Python 代码实现:
```python
def levelOrder(root):
if not root:
return []
queue = [root]
res = []
while queue:
cur_level = []
for i in range(len(queue)):
node = queue.pop(0)
cur_level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(cur_level)
return res
```
其中,root 为二叉树的根节点,res 存储最终结果,queue 存储当前层的节点。时间复杂度为 O(n),n 为节点个数。
阅读全文
相关推荐
















