Python实现完全二叉树层序遍历

在Python编程中，完全二叉树是一种特殊的二叉树结构，其中除了最后一层可能不满，其余各层都是完全填满的，且所有节点都尽可能地靠左排列。完全二叉树的层序遍历是二叉树遍历的一种常见方法，它按照从上到下、从左到右的顺序依次访问每一个节点，这对于理解和操作这种特殊结构的树非常有用。 在这个代码片段中，首先引入了`collections`模块，这是因为`deque`（双端队列）是Python标准库中的一个数据结构，用于高效地在两端进行插入和删除操作，非常适合用于层次遍历。`TreeNode`类定义了二叉树节点的基本属性，包括节点值`val`、左子节点`left`和右子节点`right`，以及构造函数来初始化这些属性。 `level_order_traversal`函数是核心部分，它接受一个二叉树的根节点作为参数。如果根节点为空，函数直接返回一个空列表，表示没有节点可遍历。接下来，初始化一个双端队列`queue`，并将根节点放入队列，同时创建一个空列表`result`来存储遍历结果。 在while循环中，只要队列非空，就持续执行以下步骤： 1. 从队列的左侧（先进先出原则）取出一个节点。 2. 将该节点的值添加到结果列表`result`中。 3. 检查当前节点是否有左子节点，如果有，则将其加入队列的右侧，以便后续处理。 4. 同样，检查当前节点是否有右子节点，如果有，也加入队列的右侧。 通过这种方式，函数确保了每个节点及其子节点都按层次顺序被正确地访问和添加到结果列表中，直到队列为空，即遍历完整个二叉树的所有层级。这个算法的时间复杂度是O(n)，其中n是二叉树的节点总数，因为每个节点恰好被访问一次。完全二叉树的这种特性使得层序遍历的过程相当直观且易于理解。