章节 28 | 面试题：二叉树层次遍历

在算法面试中，二叉树的相关问题一直是热点和难点之一，它们不仅考察了面试者对数据结构的理解深度，还检验了其递归、迭代、队列等算法思想的运用能力。其中，二叉树的层次遍历（又称广度优先遍历）是一个既基础又重要的概念，它要求按照从上到下、从左到右的顺序访问二叉树的每个节点。本章节将详细讲解二叉树层次遍历的原理、实现方法以及如何通过这种遍历方式解决面试中常见的问题。

一、层次遍历的基本概念

层次遍历，顾名思义，就是按照树的层次顺序进行遍历。对于一棵二叉树来说，就是从根节点开始，先遍历第一层（即根节点），然后逐层向下遍历，直到遍历完所有节点。这种遍历方式能够清晰地展示二叉树的层次结构，便于理解和分析。

二、层次遍历的实现方法

实现二叉树的层次遍历，主要有两种方法：迭代法和递归法（虽然递归法实现起来较为复杂且不常见，但了解其思路也有助于拓宽视野）。

2.1 迭代法

迭代法是实现层次遍历的常用方法，它依赖于队列这一数据结构。基本思路是：首先，将根节点入队；然后，当队列不为空时，执行循环操作——出队一个节点，访问该节点，并依次将其左、右子节点（如果存在）入队。这个过程会一直持续，直到队列为空，即所有节点都被访问过。

示例代码（Python）：

from collections import deque
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def levelOrderTraversal(root):
    if not root:
        return []
    queue = deque([root])  # 使用deque作为队列
    result = []
    while queue:
        level_size = len(queue)  # 当前层的节点数
        level_nodes = []  # 存储当前层的节点值
        for _ in range(level_size):
            node = queue.popleft()  # 出队
            level_nodes.append(node.val)  # 访问节点
            if node.left:
                queue.append(node.left)  # 左子节点入队
            if node.right:
                queue.append(node.right)  # 右子节点入队
        result.append(level_nodes)  # 将当前层的结果加入最终结果
    return result

2.2 递归法（非典型实现）

虽然层次遍历通常使用迭代法，但也可以通过递归结合栈或队列的模拟来实现，不过这种实现方式较为复杂且不易理解，因此在实际面试中较少采用。这里不深入展开，仅指出其存在性和可能的思路方向。

三、层次遍历的应用场景

层次遍历不仅是理解二叉树结构的一个重要工具，还在许多实际问题中有着广泛的应用。例如：

• 树的序列化与反序列化：通过层次遍历可以方便地将树结构转换为序列（如数组），并在需要时从序列中恢复树结构。
• 二叉树的最大宽度：计算二叉树每一层的节点数，从而得到树的最大宽度。这可以通过层次遍历，在遍历过程中记录每层的节点数来实现。
• 二叉树的镜像：通过层次遍历，可以在遍历过程中同时翻转每个节点的左右子节点，实现树的镜像翻转。
• 二叉树的层次和：计算二叉树每一层节点值的和，这在某些数据分析场景中非常有用。

四、面试题解析

题目：给定一棵二叉树，要求按照层次遍历的顺序返回其节点值（每一层的节点值组成一个列表）。

解题思路：

1. 初始化：创建一个空队列用于存放待访问的节点，一个空列表用于存放结果。
2. 根节点入队：将根节点加入队列。
3. 遍历队列：当队列不为空时，进行循环。
   • 记录当前队列的大小，即当前层的节点数。
   • 遍历当前层的所有节点，执行出队、访问、子节点入队操作。
   • 将当前层所有节点的值存入一个临时列表，然后将该列表添加到结果列表中。
4. 返回结果：遍历结束后，返回结果列表。

注意事项：

• 在遍历过程中，要确保先左后右地处理子节点，以保持从左到右的访问顺序。
• 使用队列可以有效地控制访问顺序，实现层次遍历的需求。

五、总结

二叉树的层次遍历是算法面试中的常见考点，掌握其实现方法不仅能够帮助我们更好地理解和分析二叉树结构，还能在处理相关问题时提供有效的解决思路。通过本章节的学习，希望大家能够熟练掌握层次遍历的迭代实现方法，并能够灵活运用到实际问题的解决中去。同时，也鼓励大家尝试探索其他可能的实现方式，如递归结合栈或队列的模拟等，以拓宽自己的算法视野。