BFS、DFS 与 Dijkstra

三种遍历,一件事:走遍所有可达状态,顺带回答一个关于「路径」或「解」的问题。BFS 像往水里扔石头,一圈圈向外扩散,读出的正是最少步数;DFS 一次扎进一条分支到底,配上回溯就能枚举出每一个子集、排列和组合;Dijkstra 则是把普通队列换成优先队列的 BFS,从而能顾及边权。这一课用同一个心智模型——一棵搜索树——把三者一并建起来,并走一遍它们各自的面试题:从层序打印,到图着色,再到整个回溯家族。

一棵搜索树,三种遍历

这一课的每道题都是穷举搜索:你在走一棵(可能是隐式的)树或图,要么读出一个最短距离,要么收集所有可能的解。三样工具的区别只在两点——访问状态的顺序,以及决定这个顺序的数据结构。

• BFS 想的是邻居和步数。往水里扔颗石头:波纹先到达一跳之外的一切,再到两跳,再到三跳。正是这种「向外扩散一圈圈」的顺序,让 BFS 在无权图上求得最短路——你第一次碰到某个点,一定是用最少的边碰到的。
• DFS 认准一条分支骑到底,再回头。preorder 是最像原始递归的遍历——先处理节点,再递归左,再递归右。当目标是「列出所有排列组合」时,DFS + 回溯天生就是这活儿的料。
• Dijkstra 是最佳优先搜索(best-first search):一个带权版 BFS,每次总是先展开距离最近的那个未完成节点。把 FIFO 队列换成优先队列,BFS 就变 Dijkstra;把所有权重都设为相等,Dijkstra 又变回 BFS。

一个具体的锚点:把一棵二叉树从上到下、从左到右地走一遍,本身就是 BFS。记住这幅画面——下面一半的题不过是这趟遍历加个花样。

BFS:层序遍历模板

BFS 全部内容就是一个队列加一个循环。先把起点塞进队列,然后反复地 poll 一个节点、offer 它未访问的邻居。把它从「平铺遍历」提升到「层序输出」的那一手,是在每层开头把队列当前大小冻结下来:此刻队列里的全部节点都属于当前层,所以一个对这个数量的 for 循环恰好把一整层排空。

public void bfs(TreeNode root) {
    if (root == null) return;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);

    while (!q.isEmpty()) {
        int size = q.size();          // 冻结本层宽度
        for (int i = 0; i < size; i++) {
            TreeNode node = q.poll();
            // 在这里访问 node.val——这是第 depth 层
            if (node.left  != null) q.offer(node.left);
            if (node.right != null) q.offer(node.right);
        }
        // 一整层处理完——depth++、关闭一个子列表等等
    }
}

判断「层到哪儿结束」有三种经典办法:开两个队列每轮交换、插哨兵(null 标记或层间的 next 指针),以及三者中最干净的——上面这个每层 size。首选 size:不用额外分配,也永远不会把哨兵和真实数据搞混。

层序遍历的花样

四道题共用这个模板,每道只改一处。

LC 102 — 二叉树层序遍历

模板原样照抄:每层开头开一个新子列表,在 for 循环里填满,循环后追加。还有一个漂亮的 DFS 解法:preorder 递归时带上 height 参数,当 height >= ans.size() 时先为这一深度建行,再追加。preorder 会先访问每行最左边的节点,所以各行按正确顺序填入——这恰好说明「层序」不一定非得用 BFS。

LC 107 — 层序遍历 II(自底向上)

和 LC 102 完全一样,末尾 Collections.reverse(ans)。别想复杂了:把你会的那道题解出来,再把结果翻过来。

LC 314 — 二叉树垂直遍历

给根列号 0,左孩子 col - 1,右孩子 col + 1,BFS 时携带一个平行的列号队列。把每个值按列号丢进 HashMap<Integer, List>,途中记录 minCol 和 maxCol,最后从左到右输出各列。这里用 BFS(而不是 DFS)很关键:它保证同一列的节点从上到下依次出来。

LC 103 — 锯齿形层序遍历

两个老实选项。偷懒的:跑 LC 102,再 Collections.reverse 奇数层(或者往每行的头部插入 list.add(0, val))。漂亮的:用一个 Deque 交替两端——从左到右的层 removeFirst 并把孩子加到尾部;从右到左的层 removeLast 并把孩子加到头部。每层翻转一个布尔。两者都是 O(n);deque 版正是面试官爱看你推的那种。

BFS 当校验器用:完全二叉树与二分图

BFS 不只用来求最短路——它逐层推进的纪律,让它天然是个一致性校验器。

LC 958 — 判断完全二叉树

完全二叉树每层都从左到右填满、中间不留空。做一次把 null 孩子也纳入的层序遍历,维护一个 metNull 标记:一旦见过 null,后面再冒出任何真实节点就证明它不是完全树。一个布尔,一趟扫。(更整洁的变体是逐节点检查两个孩子,每当「缺孩子之后又出现有孩子」时触发同一个标记。)

LC 785 — 判断二分图

一个图是二分图,当且仅当能用两种颜色染色、使得没有一条边连接同色节点。BFS 遍历图,把每个邻居染成当前节点的相反色——黑的邻居染白,白的邻居染黑。如果哪次要把某节点染成一个已经矛盾的颜色,它就不是二分图。笔记点了两个细节:用 visited/颜色数组来在有环时发现冲突;并且要对每个节点都尝试作为起点,因为图可能不连通。

Dijkstra:带优先队列的 BFS

Dijkstra 求的是带权图里从一个源点到每一个点的最短路。注意「每一个」——就算你只关心 A→B,算法也会顺带把 A→所有点算出来,因为在把每一条更短的绕行路线都排除之前,它无法确定 B 的最终答案。引擎是一个按「当前距离」排序的最小堆:反复弹出最近的未完成节点,标记为完成,然后松弛它的边(若经它走比某邻居已知的最优距离更短,就更新)。

// graph[u] = 若干 {邻居, 权重};返回从 src 出发的 dist[]
public int[] dijkstra(List<int[]>[] graph, int src, int n) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;

    // 堆里存 {node, 当前距离},按距离排序
    PriorityQueue<int[]> pq =
        new PriorityQueue<>((a, b) -> a[1] - b[1]);
    pq.offer(new int[]{src, 0});
    boolean[] visited = new boolean[n];

    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int u = cur[0];
        if (visited[u]) continue;      // 过期条目——早已敲定
        visited[u] = true;

        for (int[] edge : graph[u]) {   // edge = {v, 权重}
            int v = edge[0], w = edge[1];
            if (!visited[v] && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;               // 松弛
                pq.offer(new int[]{v, dist[v]}); // 「惰性」decrease-key
            }
        }
    }
    return dist;
}

Java 的 PriorityQueue 没有 decreaseKey,所以我们不原地更新条目——直接把带着更优距离的节点重新插入,并在弹出时跳过任何已 visited 的节点。那句 if (visited[u]) continue; 就是全部诀窍:它丢弃掉那些距离更大的过期副本。想还原真正的路径,就在 dist 旁边再维护一个 prev 映射,从目标点倒着往回走即可。

有序矩阵中第 K 小的元素(LC 378)

一个行列都有序的矩阵,是带权搜索的游乐场。最小元素在 [0][0];从任一格 [i][j] 出发,下一批候选是 [i+1][j] 和 [i][j+1]。把 [0][0] 压进最小堆,然后弹出并展开;第 k 次弹出就是答案。因为两条路径可能到同一格,用 HashSet 守卫,保证每格只入堆一次。

public int kthSmallest(int[][] matrix, int k) {
    int cols = matrix[0].length, max = matrix.length * cols;
    Set<Integer> seen = new HashSet<>();

    // 存压扁后的下标;按它指向的值排序
    PriorityQueue<Integer> pq = new PriorityQueue<>(
        (a, b) -> matrix[a / cols][a % cols] - matrix[b / cols][b % cols]);

    pq.offer(0); seen.add(0);
    for (int count = 0; count < k - 1; count++) {
        int idx = pq.poll();
        int down = idx + cols, right = idx + 1;
        if (down < max && seen.add(down))  pq.offer(down);
        // right 必须留在同一行(idx % cols != cols-1)
        if (idx % cols != cols - 1 && seen.add(right)) pq.offer(right);
    }
    int idx = pq.poll();
    return matrix[idx / cols][idx % cols];
}

压扁技巧——index = i * cols + j,再 i = index / cols、j = index % cols——让一个 int 顶替一对坐标,于是一个普通的 HashSet<Integer> 就能给格子去重(裸的 [i, j] pair 不套一个类是没法哈希的)。每次弹出最多有三格入堆,所以堆规模始终维持在 k 附近:时间 O(k log k),空间 O(k)。这就是 Dijkstra「展开 + 去重」的形状,套在一张隐式网格上。

DFS 与回溯:递归树框架

DFS 有 preorder、inorder、postorder;preorder 是读起来最像递归的那个。但 DFS 在面试里真正的价值是回溯——「返回所有子集/组合/排列」的套路。动笔之前,先画出递归树,回答三个问题:

1. 有多少层,每层是什么意思? 从上到下是递归深度。
2. 每层有几个分支? 从左到右是 for 循环。
3. 答案在哪? 每个节点,还是只在叶子?

骨架永远是 choose → recurse → un-choose:加一个候选,递归,再移除它。为什么要撤销?因为整个递归共用同一个可变缓冲区——一个 StringBuilder、一个 List。正如一位学员说得好:用共享 StringBuilder 时你改的是同一个对象,所以进下一分支前必须删掉最后一个字符;而用不可变的 str + c 拼接,每次调用都拿到一份新拷贝,无需清理。删除那一行之所以存在,纯粹是因为整个过程只有一个缓冲区。

子集:同一棵树的两种形状(LC 78)

给一组不重复的数,返回幂集。两种 DFS 形状,都是 O(2ⁿ),都值得会,因为它们的推广方向不同。

形状一——从当前往后选,答案在每个节点

每个节点,循环从 index … n-1 里选下一个元素;推进到 i + 1 意味着「不回头」,这正是让每个子集只出现一次的原因。树上每个节点都是一个合法子集,所以 res.add(...) 坐在调用的最顶上——这就是经典模板。

private void dfs(int[] nums, int index,
                 List<Integer> path, List<List<Integer>> res) {
    res.add(new ArrayList<>(path));   // 每个节点都是答案 → 深拷贝
    // base case(index 越界)隐式 return
    for (int i = index; i < nums.length; i++) {
        path.add(nums[i]);                 // 选 nums[i]
        dfs(nums, i + 1, path, res);       // 从 i+1 递归——不回头
        path.remove(path.size() - 1);   // 撤销(回溯)
    }
}

形状二——取或不取,答案在叶子

一棵严格二叉树:在下标 i,左分支「包含 nums[i]」,右分支「不包含」。只有叶子(index 越过末尾)才是完整子集,所以 res.add(...) 落在 base case 里。就算你把两个分支写反顺序,包含分支之后仍然必须撤销——回溯要求缓冲区被复原。(BFS 也能造子集,一层层地把每个部分子集扩一个元素,但两种 DFS 形状才是你在时间压力下会写的。)

组合家族(LC 77 / 39 / 40 / 216 / 22)

组合就是加了大小或和约束的子集。模板几乎不变;变的是循环的起始下标和 base case。

LC 77 — Combinations

从 1 … n 里选 k 个。用 i + 1 推进循环(顺序无关,所以绝不重用更小的下标),当 path.size() == k 时记录。

LC 39 — Combination Sum

每个数可无限次重用,所以递归用 i(不是 i + 1)以允许重选同一个元素。remain < 0 时剪枝,remain == 0 时收集。

LC 40 — Combination Sum II

每个数只用一次,而且输入有重复。两处改动:递归用 i + 1;以及先排序,再跳过重复兄弟,让同一树层的两个相等值不生出一模一样的分支。

public List<List<Integer>> combinationSum2(int[] nums, int target) {
    List<List<Integer>> res = new ArrayList<>();
    Arrays.sort(nums);                // 重复元素变相邻
    backtrack(res, new ArrayList<>(), nums, target, 0);
    return res;
}

private void backtrack(List<List<Integer>> res, List<Integer> path,
                       int[] nums, int remain, int start) {
    if (remain < 0) return;
    if (remain == 0) { res.add(new ArrayList<>(path)); return; }

    for (int i = start; i < nums.length; i++) {
        if (i > start && nums[i] == nums[i - 1]) continue; // 跳过重复兄弟
        path.add(nums[i]);
        backtrack(res, path, nums, remain - nums[i], i + 1); // i+1:每个只用一次
        path.remove(path.size() - 1);
    }
}

LC 216 — Combination Sum III

只用数字 1 … 9,每个至多一次,恰好 k 个数,和为 n。它是 LC 77 融进一个累加和:在固定的 1–9 池上用 i + 1 递归,当 path.size() == k 且余数归零时接受。

LC 22 — Generate Parentheses

n 对括号有 2n 个位置;每层在「加 (」或「加 )」上分叉。暴力会生成所有字符串再过滤,但优雅版会剪枝:只在 open < n 时才允许开括号,只在 close < open 时才允许闭括号。这两道守卫让生成的每个字符串都合法。

public List<String> generateParenthesis(int n) {
    List<String> res = new ArrayList<>();
    helper(res, new StringBuilder(), 0, 0, n);
    return res;
}

private void helper(List<String> res, StringBuilder sb,
                    int open, int close, int n) {
    if (open == n && close == n) {
        res.add(sb.toString());
        return;
    }
    if (open < n) {                       // 随时可以再开一个 '('
        sb.append('(');
        helper(res, sb, open + 1, close, n);
        sb.setLength(sb.length() - 1); // 对唯一缓冲区回溯
    }
    if (close < open) {                   // 只能闭已经开的
        sb.append(')');
        helper(res, sb, open, close + 1, n);
        sb.setLength(sb.length() - 1);
    }
}

排列与 Coin Change(LC 46 / 47 / 322)

LC 46 — Permutations

顺序算数,每个元素恰好用一次,所以树深 n,每层可以选任何还没进 path 的数。答案在叶子(path.size() == n)。最简单的守卫是 path.contains(nums[i]);一个保持长度不变的替代做法是就地 swap 元素。

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    backtrack(res, new ArrayList<>(), nums);
    return res;
}

private void backtrack(List<List<Integer>> res,
                       List<Integer> path, int[] nums) {
    if (path.size() == nums.length) {
        res.add(new ArrayList<>(path)); // 答案在叶子
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (path.contains(nums[i])) continue; // 跳过已经放进去的数
        path.add(nums[i]);
        backtrack(res, path, nums);
        path.remove(path.size() - 1);
    }
}

LC 47 — Permutations II

输入有重复。排序,带一个 used[] 数组,加上守卫 if (used[i] || (i > 0 && nums[i] == nums[i-1] && !used[i-1])) continue;。!used[i-1] 这一子句强制相等的值严格从左到右地被使用,从而塌掉那些会产生重复排列的镜像分支。

LC 322 — Coin Change

凑出金额所需的最少硬币数。笔记勾了两棵递归树:一棵是n 叉树,每个节点加一枚某面额的币;另一棵更精简,每层对应一种面额,分支是「这枚币用 0、1、2、… 次」。纯 DFS 是指数级;把它自顶向下记忆化,或自底向上 dp[i] = min(dp[i], dp[i - coin] + 1)。笔记点名的经典陷阱:DP 数组用 amount + 1 当「无穷大」哨兵,而不是 Integer.MAX_VALUE——否则转移里的 + 1 会溢出成最小的负整数,悄悄毁掉答案。

刷题清单