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

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;
}

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;
}

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;
}

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; // 实际不会执行到这里
}

// 🍊 腐烂橘子同时扩散的魔法！
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;
}

// ✈️ 像订机票一样找最便宜路径
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;
}

// 🎮 像超级玛丽一样跳跃通关！
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;
}