LeetCode 332困难高级图
重新安排行程 图解题解
这道题到底在问什么
每张机票是一条有向边，必须全部用上、且每张只用一次——这正是「欧拉路径」：一笔画走遍所有边。若有多种走法，按机场名字典序选最小的那条。
- 输入
- [[JFK,SFO],[JFK,ATL],[SFO,ATL],[ATL,JFK],[ATL,SFO]]
- 输出
- [JFK,ATL,JFK,SFO,ATL,SFO]
最优解：一步一步想明白
- 3记住三件事：① 优先走字典序最小的票 ② 走到死路就回溯入栈 ③ 最后把栈逆序。下面一步步看。
- 4这是航线图：三个机场 JFK / SFO / ATL，箭头是机票（有向）。起点 JFK 已标橙。右侧「路线栈」记录我们正踩着的路径，「已完成」是逆序收集的结果栈。
- 5先看清牌面：JFK 有 2 张票（→ATL / →SFO），ATL 有 2 张（→JFK / →SFO），SFO 有 1 张（→ATL），共 5 张。目标是把这 5 张恰好各用一次，连成一笔画。
- 6从起点 JFK 进栈，开始往外飞。站在 JFK，先看它手上还没用的票，挑目的地字典序最小的那张。
- 7站在 JFK：还没用的票通向 [ATL / SFO]（蓝色候选）。按字典序挑最小的「ATL」，准备飞 JFK → ATL（这张票就此用掉）。
- 8飞 JFK → ATL：这条边高亮，机票用掉一张。ATL 进「路线栈」，现在站到 ATL，继续在这里挑最小的票。
- 9站在 ATL：还没用的票通向 [JFK / SFO]（蓝色候选）。按字典序挑最小的「JFK」，准备飞 ATL → JFK（这张票就此用掉）。
- 10飞 ATL → JFK：这条边高亮，机票用掉一张。JFK 进「路线栈」，现在站到 JFK，继续在这里挑最小的票。
- 11站在 JFK：还没用的票通向 [SFO]（蓝色候选）。按字典序挑最小的「SFO」，准备飞 JFK → SFO（这张票就此用掉）。
- 12飞 JFK → SFO：这条边高亮，机票用掉一张。SFO 进「路线栈」，现在站到 SFO，继续在这里挑最小的票。
- 13站在 SFO：还没用的票通向 [ATL]（蓝色候选）。按字典序挑最小的「ATL」，准备飞 SFO → ATL（这张票就此用掉）。
- 14飞 SFO → ATL：这条边高亮，机票用掉一张。ATL 进「路线栈」，现在站到 ATL，继续在这里挑最小的票。
- 15站在 ATL：还没用的票通向 [SFO]（蓝色候选）。按字典序挑最小的「SFO」，准备飞 ATL → SFO（这张票就此用掉）。
- 16飞 ATL → SFO：这条边高亮，机票用掉一张。SFO 进「路线栈」，现在站到 SFO，继续在这里挑最小的票。
- 17SFO 已经没有未用的票了——这是死路。把 SFO 弹出路线栈、压进结果栈（结果栈逆序收集），回退到上一个机场看还有没有别的票。
- 18ATL 已经没有未用的票了——这是死路。把 ATL 弹出路线栈、压进结果栈（结果栈逆序收集），回退到上一个机场看还有没有别的票。
- 19SFO 已经没有未用的票了——这是死路。把 SFO 弹出路线栈、压进结果栈（结果栈逆序收集），回退到上一个机场看还有没有别的票。
- 20JFK 已经没有未用的票了——这是死路。把 JFK 弹出路线栈、压进结果栈（结果栈逆序收集），回退到上一个机场看还有没有别的票。
- 21ATL 已经没有未用的票了——这是死路。把 ATL 弹出路线栈、压进结果栈（结果栈逆序收集），回退到上一个机场看还有没有别的票。
- 22JFK 已经没有未用的票了——这是死路。把 JFK 弹出路线栈、压进结果栈（结果栈逆序收集），回退到上一个机场看还有没有别的票。
- 23五张票全部用完。把结果栈 [SFO, ATL, SFO, JFK, ATL, JFK] 逆序，就是最终行程：[JFK → ATL → JFK → SFO → ATL → SFO]。
⚠️ 容易写错的地方
✗ 错：走前先把整条路加进结果
✓ 对：走到死路（没票可走）才把机场入栈
提前入栈会漏掉还没走的支线，拼不成一笔画
✗ 错：忘了逆序
✓ 对：结果栈最后要整体反转再返回
入栈是「回溯顺序」，逆过来才是出发顺序
✗ 错：没按字典序取票
✓ 对：每次取目的地字典序最小的票
题目要求多解时返回字典序最小的行程
完整代码（Python / C++ / Java）
Python
def findItinerary(tickets):
g = defaultdict(list)
for a, b in sorted(tickets): # 按字典序排好
g[a].append(b)
res = []
def dfs(u):
while g[u]: # 还有未用的票
v = g[u].pop(0) # 取字典序最小的
dfs(v)
res.append(u) # 死路:压进结果栈
dfs("JFK")
return res[::-1] # 逆序就是答案C++
vector<string> findItinerary(vector<vector<string>>& tk){
map<string, multiset<string>> g;
for (auto& t : tk) g[t[0]].insert(t[1]); // 有序
vector<string> res;
function<void(string)> dfs = [&](string u){
while (!g[u].empty()) {
string v = *g[u].begin(); // 最小
g[u].erase(g[u].begin());
dfs(v);
}
res.push_back(u); // 入栈
};
dfs("JFK");
reverse(res.begin(), res.end());
return res;
}Java
Map<String, PriorityQueue<String>> g = new HashMap<>();
List<String> res = new LinkedList<>();
public List<String> findItinerary(List<List<String>> tk) {
for (List<String> t : tk)
g.computeIfAbsent(t.get(0), k -> new PriorityQueue<>())
.add(t.get(1)); // 小根堆=字典序
dfs("JFK");
Collections.reverse(res);
return res;
}
private void dfs(String u) {
PriorityQueue<String> pq = g.get(u);
while (pq != null && !pq.isEmpty())
dfs(pq.poll()); // 取最小的票
res.add(u); // 死路:入栈
}复杂度
时间
O(E log E)
排序/堆维护字典序，E 条机票各处理一次
空间
O(E)
邻接表存 E 条边 + 递归栈 + 结果栈
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 重新安排行程 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
和普通 DFS 求路径有什么区别？+
普通 DFS 找一条简单路径，这里要用光所有边（欧拉路径）。关键差异是「走到死路才入栈 + 最后逆序」，靠回溯把所有支线都串进来。
怎么保证字典序最小？+
让每个机场的出边按字典序有序（排序 / multiset / 小根堆），每次都取最小的那条票先走即可。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 重新安排行程 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。