回溯困难2 种解法

#332重新安排行程

从 JFK 出发使用全部机票恰好一次，并返回字典序最小的有效行程。

#回溯#图#欧拉路径#优先队列

解题主线

旧文件名中的 Q322 是误标，题意和示例对应 LeetCode 332。

回溯法必须按目的机场字典序尝试同一起点的边，首个完整路径才是字典序最小答案。

把机票视为有向多重图后，可用 Hierholzer 算法在线性次取边中构造欧拉路径；最小堆负责词法序。

解法 1：排序后回溯

把机票按出发地、目的地排序，使用 used 下标逐张尝试；由于候选目的地有序，第一个完整路径即答案。

时间复杂度

O(E log E + E × E!)，最坏情况下回溯枚举机票排列

空间复杂度

O(E)，不计输入副本

332. 重新安排行程 · 排序后回溯

java

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

final class Solution {
    public List<String> findItinerary(List<List<String>> tickets) {
        List<List<String>> ordered = new ArrayList<>(tickets);
        ordered.sort(Comparator.comparing((List<String> ticket) -> ticket.get(0))
                .thenComparing(ticket -> ticket.get(1)));
        List<String> path = new ArrayList<>(tickets.size() + 1);
        path.add("JFK");
        if (!backtrack(ordered, new boolean[ordered.size()], path)) {
            throw new IllegalArgumentException("no valid itinerary");
        }
        return path;
    }

    private boolean backtrack(List<List<String>> tickets, boolean[] used, List<String> path) {
        if (path.size() == tickets.size() + 1) {
            return true;
        }
        String from = path.get(path.size() - 1);
        for (int i = 0; i < tickets.size(); i++) {
            List<String> ticket = tickets.get(i);
            if (used[i] || !ticket.get(0).equals(from)) {
                continue;
            }
            used[i] = true;
            path.add(ticket.get(1));
            if (backtrack(tickets, used, path)) {
                return true;
            }
            path.remove(path.size() - 1);
            used[i] = false;
        }
        return false;
    }
}

把机票按出发地、目的地排序，使用 used 下标逐张尝试；由于候选目的地有序，第一个完整路径即答案。

保留旧实现的回溯思路，但补齐了目的地词法排序和调用级状态隔离。

解法 2：Hierholzer + 最小堆

为每个出发机场建立目的地最小堆，持续取词法序最小的未用边；无边可走时将节点加入路径头部。

时间复杂度

O(E log E)，每张机票入堆、出堆各一次

空间复杂度

O(E)，图、递归栈和结果均与机票数同阶

332. 重新安排行程 · Hierholzer + 最小堆

java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

final class Solution {
    public List<String> findItinerary(List<List<String>> tickets) {
        Map<String, PriorityQueue<String>> graph = new HashMap<>();
        for (List<String> ticket : tickets) {
            graph.computeIfAbsent(ticket.get(0), ignored -> new PriorityQueue<>())
                    .offer(ticket.get(1));
        }

        Deque<String> stack = new ArrayDeque<>();
        Deque<String> route = new ArrayDeque<>();
        stack.push("JFK");
        while (!stack.isEmpty()) {
            String airport = stack.peek();
            PriorityQueue<String> destinations = graph.get(airport);
            if (destinations != null && !destinations.isEmpty()) {
                stack.push(destinations.poll());
            } else {
                route.addFirst(stack.pop());
            }
        }
        if (route.size() != tickets.size() + 1) {
            throw new IllegalArgumentException("no valid itinerary");
        }
        return new ArrayList<>(route);
    }
}

为每个出发机场建立目的地最小堆，持续取词法序最小的未用边；无边可走时将节点加入路径头部。

这是与逐票回溯真正不同的欧拉路径解法，适合机票数量较大时使用。

边界与易错点

只按出发机场排序不能保证同一起点的目的机场按词法序选择。
重复机票是不同的边；回溯要按下标标记，图解法则必须在堆中保留重复目的地。
结果、path 和 used 不能留作实例字段，否则重复调用会残留旧行程。
Hierholzer 得到的是逆后序：走到无边可用时把机场加入结果头部，而不是访问时立即加入。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

backtrack/Q322_findItinerary.java