二叉树层序遍历算法

二叉树是一种常见的数据结构，在计算机算法中得到了广泛的应用。层序遍历是二叉树遍历算法中的一种，也称为广度优先遍历。它的思路是按照二叉树从上到下、从左到右的顺序遍历，能够将节点按照层次分组输出，也是一种比较容易理解和实现的二叉树遍历算法。

层序遍历的基本实现

层序遍历可以使用队列来实现，具体步骤如下：

1.将二叉树的根节点入队；

2.循环执行如下操作，直到队列为空时停止：

(1) 将队首节点提取并输出；

(2) 将队首节点的左孩子入队；

(3) 将队首节点的右孩子入队；

层序遍历代码如下：

```python

def levelOrder(root):

if not root:

return []

result, cur_level = [], [root]

while cur_level:

next_level, cur_res = [], []

for node in cur_level:

cur_res.append(node.val)

if node.left:

next_level.append(node.left)

if node.right:

next_level.append(node.right)

result.append(cur_res)

cur_level = next_level

return result

```

层序遍历的时间和空间复杂度

层序遍历会遍历二叉树的所有节点，因此时间复杂度和节点数成正比，即 O(n)。另外，层序遍历还需要使用队列来辅助遍历，队列里最多会存储一层的节点，因此空间复杂度为 O(w)，其中 w 为树的最大宽度。

层数和宽度存在题目，题目的例子是：

```python

# Definition for a binary tree node.

# class TreeNode(object):

# def __init__(self, x):

# self.val = x

# self.left = None

# self.right = None

class Solution(object):

def widthOfBinaryTree(self, root):

"""

:type root: TreeNode

:rtype: int

"""

if not root:

return 0

cur_level, max_width = [(root, 0)], 0

while cur_level:

next_level = []

max_width = max(max_width, cur_level[-1][1] - cur_level[0][1] + 1)

for node, pos in cur_level:

if node.left:

next_level.append((node.left, pos * 2))

if node.right:

next_level.append((node.right, pos * 2 + 1))

cur_level = next_level

return max_width

```

层序遍历的应用

层序遍历可以用于以下场景：

1.求二叉树最大深度：可以通过层序遍历求出二叉树的深度，从而得到二叉树的最大深度；

2.二叉树的序列化和反序列化：通过层序遍历将二叉树序列化成字符串，再通过反序列化重新构造二叉树；

3.判断二叉树是否是完全二叉树：对于一个节点数为 n 的二叉树，若按照层序遍历将其所在的位置编号，则编号为 i 的节点应该满足如下条件：

(i) 当 i 的左右子树都有时，左子树的编号为 2i，右子树的编号为 2i+1；

(ii) 当 i 的左子树有而右子树没有时，编号为 2i；

(iii) 当 i 的左子树没有而右子树有时，不符合完全二叉树的性质。

因此，可以通过层序遍历判断二叉树是否为完全二叉树。