重新安排行程

最直觉的想法：每一步都挑字典序最小的下一站。换一组票看得最清楚：JFK→KUL、JFK→NRT、NRT→JFK。从 JFK 贪心选最小的 KUL，一步就走到 KUL——可 KUL 没有任何出票，当场卡死，手里还攥着 JFK→NRT、NRT→JFK 两张没用（只用了 1 张 / 共 3 张）。贪心一头扎进死路，没法回头补票。

正解叫 Hierholzer：每个机场的目的地按字典序排好，一路往最小的走、走过的票当场撕掉；一旦某机场再也走不动了，就把它压进答案栈。等递归全部回弹，把答案栈倒过来，就是字典序最小的一笔画。

建图 · 每个机场的目的地按字典序排队：先把五张票按出发地归类，每个出发地的目的地从小到大排好队。JFK 能去 ATL 和 SFO，ATL 能去 JFK 和 SFO，SFO 能去 ATL。从 JFK 起步，下一步永远先挑队首那个最小的。

走第 1 步 · JFK 撕掉去 ATL 的票：站在 JFK，队首是 ATL，走过去，把 JFK 到 ATL 这张票撕掉。注意 JFK 的队列只剩 SFO 了。现在递归进入 ATL。

走第 2 步 · ATL 撕掉去 JFK 的票：在 ATL，它的队首是 JFK（比 SFO 小），走回 JFK，撕掉 ATL 到 JFK 这张票。ATL 队列只剩 SFO。注意我们绕回了 JFK——但 JFK 还有去 SFO 的票没用，所以不是死路。

走第 3 步 · JFK 撕掉去 SFO 的票：又回到 JFK，它的队列现在只剩 SFO，走过去，撕掉 JFK 到 SFO。JFK 队列空了——但 JFK 是要等所有递归回弹后最后才结算的，先继续往 SFO 钻。

走第 4 步 · SFO 撕掉去 ATL 的票：在 SFO，队首是 ATL，走过去撕掉 SFO 到 ATL。SFO 队列空了。继续钻进 ATL，它还剩最后一张 ATL 到 SFO。

走第 5 步 · ATL 撕掉最后一张去 SFO：在 ATL，撕掉最后一张 ATL 到 SFO，走到 SFO。此刻五张票全部撕完，图上没有任何剩余的边。现在到 SFO，它前面已经走过、队列是空的——死路来了。

死路落地 · SFO 第一个进答案栈：SFO 队列空、走不动了，于是把 SFO 压进答案栈。这就是 Hierholzer 的灵魂：最先卡死的机场，最先落进答案栈、最后才会被倒序输出。SFO 注定是行程的终点。

回弹 · ATL 也走不动 → 入栈：递归回弹到刚才那个 ATL，它的票早撕光、队列空，于是 ATL 也压进答案栈。注意入栈顺序：先 SFO 后 ATL，但因为是栈，ATL 现在压在 SFO 上面。

回弹 · SFO、JFK、ATL、JFK 依次入栈：继续往回弹：上一层的 SFO 入栈、再上层第一次到的 JFK 入栈、再上层的 ATL 入栈，最后回到起点 JFK 入栈。每一层都是因为队列已空才落地，顺序是 SFO、ATL、SFO、JFK、ATL、JFK。

收束 · 把答案栈倒过来：答案栈从底到顶是 SFO、ATL、SFO、JFK、ATL、JFK，倒过来读，就是 JFK 到 ATL 到 JFK 到 SFO 到 ATL 到 SFO。一笔画完成，五张票全用光，且字典序最小。

一句话记牢：目的地按字典序排队，一路撕票往最小走；谁先卡死谁先进答案栈，最后把栈倒过来读，就是字典序最小的一笔画。

边界三连：边界先过：单张票递归一层就落地；重复票要当成多条平行边各存一次；那个只进不出的机场，注定是整条行程的终点。

雷区实演 · 纯贪心一头扎进死路：用一组真会翻车的票实演：JFK→KUL、JFK→NRT、NRT→JFK。纯贪心从 JFK 选字典序更小的 KUL，一步就走到 KUL——而 KUL 没有任何出票，当场卡死，手里还剩 JFK→NRT、NRT→JFK 两张废了（只用 1 张 / 共 3 张）。正解 Hierholzer 会得到 JFK→NRT→JFK→KUL。贪心一步选小废掉回程票，这才是必须用后序回溯的真理由。

面试追问 1：面试常追这个“为什么对”。核心：每条边只撕一次，递归保证走光出边后才落地，逆序天然是合法欧拉路径。

面试追问 2：进阶追问复杂度。可以预排序加指针消费，把每步取最小做成常数，思路和堆等价但常数更优。

面试追问 3：重新安排行程不是孤题，它是欧拉路径一笔画的代表。认出“用光所有边”这个信号，就该想到 Hierholzer。

学完别乱跳，去高级图专题连刷同类一笔画与图遍历题：/leetcode-animation/ds?k=graph。卡住时用 AI 助教小欧问一句“我的后序落地写成前序了吗”，它会顺着你的代码帮你定位。