数据结构二叉树的层序遍历

叉树的层序遍历是一种按照从上到下、从左到右的顺序访问二叉树节点的方法。通过层序遍历，我们可以逐层遍历二叉树的节点，并在遍历过程中进行判断，从而确定二叉树是否为完全二叉树。层序遍历是一种广度优先搜索的遍历方式，适用于树结构。通过利用队列实现层序遍历，我们可以按照从上到下、从左到右的顺序逐层遍历树中的节点。具体实现方法如下：

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 = []
        for i 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

以上代码中，我们定义了一个`TreeNode`类来表示二叉树的节点，`levelOrder`函数用于实现二叉树的层序遍历。在函数中，我们首先判断根节点是否为空，如果为空则直接返回空列表。然后定义一个`res`列表来存储遍历结果，定义一个`queue`队列来存储待遍历的节点。接下来，我们使用一个`while`循环来遍历整个二叉树。在每一层遍历中，我们定义一个`level`列表来存储当前层的节点值，然后使用一个`for`循环来遍历当前层的所有节点。在循环中，我们首先弹出队列中的第一个节点，并将其值加入到`level`列表中。然后判断该节点是否有左右子节点，如果有则将其左右子节点加入到队列中。最后将`level`列表加入到`res`列表中，表示当前层的遍历已经完成。最终返回`res`列表即可。