算法精讲 | 树（二）：BFS层序遍历の魔法——像水波纹一样扫描整棵树

发布于：2025-03-15 ⋅ 阅读:(21) ⋅ 点赞:(0)

🎯 算法精讲 | 树（二）：BFS层序遍历の魔法——像水波纹一样扫描整棵树

📅 2025/03/11 || 推荐阅读时间 12分钟

🌟 开篇故事

小明用DFS解二叉树的右视图总超时，直到他发现BFS层序遍历就像超市结账时排队——先来的顾客先结账，每批结账的顾客正好组成一个层级！今天我们就来揭秘这个波纹扫描术的奥义！

🌟 导航图

在这里插入图片描述

一、BFS 核心原理（图解版）

1.1 队列工作原理 🧩

在这里插入图片描述

1.2 与DFS的核心差异表

特性 BFS DFS
数据结构 队列（Queue） 栈（Stack）
遍历顺序 层级扩散 深度优先
空间复杂度 O(最宽层节点数) O(树的高度)
经典应用场景 最短路径、层序操作 路径遍历、回溯问题
力扣经典题 102.层序遍历 113.路径总和II

二、3大变形题型库

2.1 基础层序遍历 🔗力扣102

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
  
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root); // 🚀 启动引擎！
  
    while (!queue.isEmpty()) {
        int levelSize = queue.size(); // 📌 重点！必须在此处获取size
        List<Integer> level = new ArrayList<>();
  
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            // 🌈 像播种机一样播撒下一层
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        res.add(level); // 🎁 打包当前层结果
    }
    return res;
}

2.2 锯齿形遍历 🔗力扣103

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
  
    boolean isEvenLevel = false; // 🎭 奇偶层标记
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
  
    while (!queue.isEmpty()) {
        int size = queue.size();
        LinkedList<Integer> level = new LinkedList<>(); // 🪄 魔法发生地！
  
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            if (isEvenLevel) {
                level.addFirst(node.val); // 🔙 偶数层反向插入
            } else {
                level.addLast(node.val);  // ➡️ 奇数层正向插入
            }
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        res.add(level);
        isEvenLevel = !isEvenLevel; // 🔄 切换标记
    }
    return res;
}

2.3 层最大值 🔗力扣515

public List<Integer> largestValues(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
  
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
  
    while (!queue.isEmpty()) {
        int size = queue.size();
        int max = Integer.MIN_VALUE; // 🌋 初始化火山口
  
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            max = Math.max(max, node.val); // 🏆 实时更新最大值
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        res.add(max); // 📌 记录本层巅峰值
    }
    return res;
}

三、高频场景避坑指南

3.1 特殊场景处理表

特殊场景 易错点 解决方案
N叉树层序遍历 子节点是List结构 遍历 children列表
最小深度计算 过早返回导致错误 遇到叶子节点才更新结果
图结构中的BFS 循环引用导致死循环 使用 visited集合标记已访问
双向BFS优化 两端扩散的终止条件 检测到相交元素立即返回

3.2 最小深度问题 🔗力扣111

public int minDepth(TreeNode root) {
    if (root == null) return 0;
  
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    int depth = 0; // 🌊 波纹扩散计数器
  
    while (!queue.isEmpty()) {
        depth++; // 📈 层级+1
        int size = queue.size();
  
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            // 🎯 遇到第一个叶子节点立即返回
            if (node.left == null && node.right == null) return depth;
  
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
    }
    return depth; // 实际不会执行到这里
}

四、可视化进阶：双向BFS动图

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

适用场景：当起点和终点都明确时（如127.单词接龙），时间复杂度从O(bd)降到O(b(d/2))！

五、知识宇宙扩展站 🚀

5.1 BFS变种应用表

变种类型 核心思想 经典题目
多源BFS 多个起点同时扩散 994.腐烂的橘子
优先队列BFS 带权重的最短路径 787.K站中转内最便宜的航班
跳跃式BFS 允许跨层访问 1345.跳跃游戏IV

5.2 多源BFS实战 🔥 🔗力扣994

// 🍊 腐烂橘子同时扩散的魔法！
public int orangesRotting(int[][] grid) {
    Queue<int[]> queue = new LinkedList<>();
    int fresh = 0, time = 0;
  
    // 🌋 初始化：所有腐烂橘子入队
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == 2) queue.offer(new int[]{i, j});
            else if (grid[i][j] == 1) fresh++;
        }
    }
  
    int[][] dirs = {{1,0}, {-1,0}, {0,1}, {0,-1}};
    while (!queue.isEmpty() && fresh > 0) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            int[] pos = queue.poll();
            for (int[] d : dirs) {
                int x = pos[0] + d[0];
                int y = pos[1] + d[1];
                if (x >= 0 && x < grid.length && y >= 0 && y < grid[0].length 
                    && grid[x][y] == 1) {
                    grid[x][y] = 2;
                    queue.offer(new int[]{x, y});
                    fresh--;
                }
            }
        }
        time++; // ⏳ 时间流逝
    }
    return fresh == 0 ? time : -1;
}

5.3 带权BFS专题 ⚖️

5.3.1 优先队列BFS模板 ⚖️ 🔗力扣787
// ✈️ 像订机票一样找最便宜路径
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
    Map<Integer, List<int[]>> graph = new HashMap<>();
    for (int[] f : flights) {
        graph.computeIfAbsent(f[0], key -> new ArrayList<>()).add(new int[]{f[1], f[2]});
    }
  
    // 优先队列：按价格排序（三元组：当前节点，剩余次数，累计价格）
    PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> a[2]-b[2]);
    pq.offer(new int[]{src, k+1, 0});
  
    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int node = curr[0], stops = curr[1], price = curr[2];
  
        if (node == dst) return price;
        if (stops == 0) continue;
  
        for (int[] neighbor : graph.getOrDefault(node, new ArrayList<>())) {
            pq.offer(new int[]{neighbor[0], stops-1, price + neighbor[1]});
        }
    }
    return -1;
}
5.3.2 复杂度对比表
算法类型 时间复杂度 空间复杂度 适用场景
传统BFS O(n) O(n) 无权图最短路径
优先队列BFS O(m + n log n) O(n) 带权图最优路径
双向BFS O(b^(d/2)) O(b^(d/2)) 起点终点明确的场景

5.4 跳跃式BFS黑科技 🦘

5.4.1 跳跃游戏IV 🔗力扣1345
// 🎮 像超级玛丽一样跳跃通关！
public int minJumps(int[] arr) {
    Map<Integer, List<Integer>> valueMap = new HashMap<>();
    for (int i = 0; i < arr.length; i++) {
        valueMap.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);
    }
  
    Queue<Integer> queue = new LinkedList<>();
    boolean[] visited = new boolean[arr.length];
    queue.offer(0);
    visited[0] = true;
    int steps = 0;
  
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            int curr = queue.poll();
            if (curr == arr.length - 1) return steps;
    
            // 三种跳法：左跳、右跳、等值跳
            if (curr - 1 >= 0 && !visited[curr-1]) {
                visited[curr-1] = true;
                queue.offer(curr-1);
            }
            if (curr + 1 < arr.length && !visited[curr+1]) {
                visited[curr+1] = true;
                queue.offer(curr+1);
            }
            if (valueMap.containsKey(arr[curr])) {
                for (int same : valueMap.get(arr[curr])) {
                    if (!visited[same]) {
                        visited[same] = true;
                        queue.offer(same);
                    }
                }
                valueMap.remove(arr[curr]); // 🗝️ 关键优化！
            }
        }
        steps++;
    }
    return -1;
}
5.4.2 优化技巧对比
优化方法 效果提升 实现难度
哈希预存等值节点 减少重复搜索 ⭐⭐
访问后立即删除键 避免重复处理同类节点 ⭐⭐⭐
方向剪枝 优先处理更接近终点的方向 ⭐⭐

六、BFS 灵魂十问 💬

Q1：如何处理图遍历中的循环引用？

答：使用 visited集合，像贴封条一样标记已访问节点！

Q2：什么时候必须用BFS不能用DFS？

答：找最短路径时（如迷宫问题），BFS像警犬搜救，DFS像游客瞎逛！

Q3：队列实现选LinkedList还是ArrayDeque？

答：99%场景用 ArrayDeque更高效，但需要头尾操作时用 LinkedList！

Q4：N叉树层序遍历和二叉树有什么区别？

答：遍历子节点时从固定左右子节点变成遍历 children列表！

Q5：如何判断BFS遍历是否完成？

答：队列空且所有节点处理完毕，就像快递站所有包裹都派送完！

六、课后作业大闯关 🏁

6.1 必做题

6.2 挑战题

6.3 基础关：层序遍历变种

6.4 进阶关：多维BFS

6.5 终极关：BFS+状态压缩

七、灵魂拷问小剧场 🎭

小白：BFS层序遍历的时间复杂度怎么计算？

大佬：每个节点进出队列各一次，时间复杂度是妥妥的O(n)！

小白：那空间复杂度呢？

大佬：最差情况是完美二叉树，最后一层有⌈n/2⌉个节点，所以是O(n)！

八、下期预告

《树的删除操作——像外科手术一样精准移除节点》 🔥 亮点抢先看：

  • 🪓 目标节点的精准定位术
  • 🔧 子树重组缝合技巧
  • 🩺 AVL树平衡性维护

🌟 算法留言墙：欢迎在评论区留下你的BFS实战故事

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布