重新安排行程 图解题解

这道题到底在问什么

机票

JFK→SFO, JFK→ATL, SFO→ATL, ATL→JFK, ATL→SFO

输出

JFK → ATL → JFK → SFO → ATL → SFO

最优解：一步一步想明白

1. 3最直觉的想法：每一步都挑字典序最小的下一站。换一组票看得最清楚：JFK→KUL、JFK→NRT、NRT→JFK。从 JFK 贪心选最小的 KUL，一步就走到 KUL——可 KUL 没有任何出票，当场卡死，手里还攥着 JFK→NRT、NRT→JFK 两张没用（只用了 1 张 / 共 3 张）。贪心一头扎进死路，没法回头补票。
2. 4正解叫 Hierholzer：每个机场的目的地按字典序排好，一路往最小的走、走过的票当场撕掉；一旦某机场再也走不动了，就把它压进答案栈。等递归全部回弹，把答案栈倒过来，就是字典序最小的一笔画。
3. 5JFK: [ATL, SFO]　ATL: [JFK, SFO]　SFO: [ATL]先把五张票按出发地归类，每个出发地的目的地从小到大排好队。JFK 能去 ATL 和 SFO，ATL 能去 JFK 和 SFO，SFO 能去 ATL。从 JFK 起步，下一步永远先挑队首那个最小的。
4. 6在 JFK，取队首 ATL，走过去并撕票站在 JFK，队首是 ATL，走过去，把 JFK 到 ATL 这张票撕掉。注意 JFK 的队列只剩 SFO 了。现在递归进入 ATL。
5. 7在 ATL，取队首 JFK，撕票回到 JFK在 ATL，它的队首是 JFK（比 SFO 小），走回 JFK，撕掉 ATL 到 JFK 这张票。ATL 队列只剩 SFO。注意我们绕回了 JFK——但 JFK 还有去 SFO 的票没用，所以不是死路。
6. 8在 JFK，队首只剩 SFO，撕票走向 SFO又回到 JFK，它的队列现在只剩 SFO，走过去，撕掉 JFK 到 SFO。JFK 队列空了——但 JFK 是要等所有递归回弹后最后才结算的，先继续往 SFO 钻。
7. 9在 SFO，队首 ATL，撕票走向 ATL在 SFO，队首是 ATL，走过去撕掉 SFO 到 ATL。SFO 队列空了。继续钻进 ATL，它还剩最后一张 ATL 到 SFO。
8. 10在 ATL，撕掉 ATL→SFO，五张票全部用光在 ATL，撕掉最后一张 ATL 到 SFO，走到 SFO。此刻五张票全部撕完，图上没有任何剩余的边。现在到 SFO，它前面已经走过、队列是空的——死路来了。
9. 11SFO 走不动 → 压入答案栈　栈：[SFO]SFO 队列空、走不动了，于是把 SFO 压进答案栈。这就是 Hierholzer 的灵魂：最先卡死的机场，最先落进答案栈、最后才会被倒序输出。SFO 注定是行程的终点。
10. 12退回 ATL，队列已空 → 入栈　栈：[SFO, ATL]递归回弹到刚才那个 ATL，它的票早撕光、队列空，于是 ATL 也压进答案栈。注意入栈顺序：先 SFO 后 ATL，但因为是栈，ATL 现在压在 SFO 上面。
11. 13继续回弹，每层队列都空 → 逐个入栈继续往回弹：上一层的 SFO 入栈、再上层第一次到的 JFK 入栈、再上层的 ATL 入栈，最后回到起点 JFK 入栈。每一层都是因为队列已空才落地，顺序是 SFO、ATL、SFO、JFK、ATL、JFK。
12. 14答案 = JFK → ATL → JFK → SFO → ATL → SFO答案栈从底到顶是 SFO、ATL、SFO、JFK、ATL、JFK，倒过来读，就是 JFK 到 ATL 到 JFK 到 SFO 到 ATL 到 SFO。一笔画完成，五张票全用光，且字典序最小。
13. 17一句话记牢：目的地按字典序排队，一路撕票往最小走；谁先卡死谁先进答案栈，最后把栈倒过来读，就是字典序最小的一笔画。
14. 20另一组票：JFK→KUL / JFK→NRT / NRT→JFK　贪心选小的 KUL，一步卡死用一组真会翻车的票实演：JFK→KUL、JFK→NRT、NRT→JFK。纯贪心从 JFK 选字典序更小的 KUL，一步就走到 KUL——而 KUL 没有任何出票，当场卡死，手里还剩 JFK→NRT、NRT→JFK 两张废了（只用 1 张 / 共 3 张）。正解 Hierholzer 会得到 JFK→NRT→JFK→KUL。贪心一步选小废掉回程票，这才是必须用后序回溯的真理由。
15. 27学完别乱跳，去高级图专题连刷同类一笔画与图遍历题：/leetcode-animation/ds?k=graph。卡住时用 AI 助教小欧问一句“我的后序落地写成前序了吗”，它会顺着你的代码帮你定位。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def findItinerary(self, tickets):
        from collections import defaultdict
        graph = defaultdict(list)
        # 逆序排序后 append，pop() 末尾即取到字典序最小
        for a, b in sorted(tickets, reverse=True):
            graph[a].append(b)
        route = []
        def dfs(airport):
            while graph[airport]:          # 还有票就一直走
                dfs(graph[airport].pop())  # 撕票 + 递归进入
            route.append(airport)          # 走不动了再落地
        dfs("JFK")
        return route[::-1]                 # 后序逆序即答案

class Solution {
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        unordered_map<string, priority_queue<string, vector<string>, greater<string>>> g;
        for (auto& t : tickets) g[t[0]].push(t[1]);  // 小根堆=字典序最小先出
        vector<string> route;
        function<void(const string&)> dfs = [&](const string& u) {
            auto& pq = g[u];
            while (!pq.empty()) {
                string v = pq.top(); pq.pop();      // 撕票
                dfs(v);
            }
            route.push_back(u);                     // 死路落地
        };
        dfs("JFK");
        reverse(route.begin(), route.end());
        return route;
    }
};

class Solution {
    Map<String, PriorityQueue<String>> graph = new HashMap<>();
    LinkedList<String> route = new LinkedList<>();
    public List<String> findItinerary(List<List<String>> tickets) {
        for (List<String> t : tickets)
            graph.computeIfAbsent(t.get(0), k -> new PriorityQueue<>()).offer(t.get(1));
        dfs("JFK");
        return route;
    }
    private void dfs(String u) {
        PriorityQueue<String> pq = graph.get(u);
        while (pq != null && !pq.isEmpty()) dfs(pq.poll());  // 撕票+递归
        route.addFirst(u);   // 死路落地：直接插到行程头部
    }
}

# 1. 建图：每个出发点的目的地按【字典序/题目要求】排好
graph = defaultdict(____)        # 列表(逆序排+pop) 或 最小堆
for a, b in edges: graph[a].___(b)

route = []
def dfs(u):
    while graph[u]:              # 还有未用的出边就继续
        dfs(graph[u].____())     # 撕掉这条边再递归
    route.append(u)             # ★走不动了才后序落地★

dfs(起点)
return route[::-1]              # 逆序即一笔画

// 1. 建图：出边用小根堆保证字典序
unordered_map<string, priority_queue<string,vector<string>,greater<>>> g;
// for (auto& e : edges) g[e.from].push(e.to);
vector<string> route;
function<void(const string&)> dfs = [&](const string& u){
    while (!g[u].empty()) {              // 还有出边
        auto v = g[u].top(); g[u].pop();  // 撕边
        dfs(v);
    }
    route.push_back(u);                 // ★后序落地★
};
dfs(start); reverse(route.begin(), route.end());

// 1. 建图：出边用 PriorityQueue 保证字典序
Map<String,PriorityQueue<String>> g = new HashMap<>();
// for (e : edges) g.computeIfAbsent(e.from,k->new PriorityQueue<>()).offer(e.to);
LinkedList<String> route = new LinkedList<>();
void dfs(String u){
    PriorityQueue<String> pq = g.get(u);
    while (pq != null && !pq.isEmpty()) dfs(pq.poll());  // 撕边+递归
    route.addFirst(u);   // ★后序落地：往头部插★
}

复杂度

面试官可能追问