层次遍历二叉树算法python

2024年2月7日发(作者：)

层次遍历二叉树算法python

层次遍历二叉树算法python

介绍

二叉树是一种常见的数据结构，它由节点组成，每个节点最多有两个子节点。在二叉树中，我们经常需要遍历整棵树来查找或处理节点。层次遍历是一种广度优先的遍历方式，它从上到下、从左到右逐层访问二叉树的所有节点。本文将介绍如何使用Python实现层次遍历二叉树算法。

算法原理

层次遍历二叉树算法可以使用队列来实现。首先将根节点入队列，然后每次出队列一个节点时，将其左右子节点入队列。这样就可以按照从上到下、从左到右的顺序依次访问所有节点。

代码实现

以下是使用Python实现层次遍历二叉树算法的代码：

```python

class TreeNode:

def __init__(self, val=0, left=None, right=None):

= val

= left

= right

def levelOrder(root: TreeNode) -> List[List[int]]:

if not root:

return []

queue = [root]

res = []

while queue:

n = len(queue)

level = []

for i in range(n):

node = (0)

()

if :

()

if :

()

(level)

return res

```

代码解析

首先定义了一个TreeNode类，表示二叉树的节点。每个节点包含三个属性：val表示节点的值，left表示左子节点，right表示右子节点。

levelOrder函数是实现层次遍历的主函数。它接受一个TreeNode类型的参数root，表示二叉树的根节点。如果根节点为空，则直接返回空列表。

定义一个队列queue，并将根节点入队列。

定义一个空列表res，用于存储遍历结果。

进入循环，当队列不为空时执行以下操作：

获取当前队列中的元素个数n。

定义一个空列表level，用于存储当前层级的所有节点值。

依次出队列n个元素，并将它们的值添加到level列表中。同时将它们

的左右子节点入队列。

将level列表添加到res列表中，表示当前层级已经遍历完成。

返回res列表作为遍历结果。

总结

本文介绍了如何使用Python实现层次遍历二叉树算法。该算法使用队列来实现广度优先遍历，从上到下、从左到右依次访问所有节点。在实际应用中，这种遍历方式可以用于查找或处理二叉树中特定条件下的节点。