6-2 二叉树的层次遍历
时间: 2023-09-03 22:12:50 浏览: 62
二叉树的层次遍历是一种广度优先遍历的方式,可以按照从上到下、从左到右的顺序遍历二叉树的所有节点。具体实现方法可以使用队列来辅助实现。
算法步骤如下:
1. 如果根节点为空,则返回空列表。
2. 创建一个队列,并将根节点入队。
3. 当队列不为空时,重复以下步骤:
- 从队列中取出一个节点,将其值存储到结果列表中。
- 如果该节点有左子树,则将左子树入队。
- 如果该节点有右子树,则将右子树入队。
4. 返回结果列表。
下面是一个示例代码实现:
```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 _ 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
```
该函数接受一个根节点作为参数,返回一个列表,其中每个元素表示二叉树的一层。每层的节点值按照从左到右的顺序存储在列表中。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)