12. 二叉树-BFS

正文

二叉树的广度优先搜索（BFS）通常用于层序遍历（Level-order Traversal）。它的特点是按照从上到下、从左到右的顺序逐层访问节点。

算法模板

import java.util.ArrayDeque

fun bfs(root: TreeNode?) {
    if (root == null) return
    
    // 使用队列保存每一层的节点
    val queue = ArrayDeque<TreeNode>()
    queue.offer(root)
    
    while (queue.isNotEmpty()) {
        // 当前层的节点数量
        val levelSize = queue.size
        
        // 遍历当前层的所有节点
        for (i in 0 until levelSize) {
            val node = queue.poll()
            visit(node)

            // 将下一层的节点入队
            node.left?.let { queue.offer(it) }
            node.right?.let { queue.offer(it) }
        }
    }
}

使用说明

1. 核心技巧：

   • 队列（Queue）：利用队列的“先进先出”特性。
   • **levelSize**：通过记录当前队列的大小，可以精确控制每一层节点的遍历，适用于需要区分层级的题目。

2. 常见变形：

   • 层平均值：在遍历每一层时计算平均值。
   • 右视图：每一层遍历的最后一个节点即为右视图可见节点。
   • Z 字形遍历：利用双端队列或在输出结果时进行翻转。
   • 寻找最小深度：第一个到达叶子节点时的层数即为最小深度。

3. 性能分析：

   • 时间复杂度：$O(N)$。
   • 空间复杂度：$O(W)$，其中 $W$ 是二叉树的最大宽度。在完全二叉树中，最后一层节点数约为 $N/2$。

4. 注意点：

   • 在 Kotlin 中，ArrayDeque 是实现队列的最佳选择。
   • 入队前务必检查子节点是否为空。