算法精讲 | 树（二）：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(); // 📌 重点！必须在此处获取sizeList<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++; // 📈 层级+1int 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;
}