What is the main pattern used in Reconstruct Itinerary?

The primary pattern is depth-first search on a directed graph to form an Eulerian path while respecting lexical order.

Why is sorting destinations important?

Sorting ensures that among multiple possible flights, the itinerary with the smallest lexical order is chosen consistently.

Can I use BFS instead of DFS for this problem?

DFS is preferred because it naturally handles backtracking and constructing the Eulerian path correctly.

How do I handle tickets with the same departure?

Maintain a sorted list of destinations for each departure and remove edges as tickets are used to avoid duplicates.

What should I do if the itinerary appears reversed?

Prepend nodes during backtracking instead of appending to build the correct order from start to end.

#332

Hard

auto_awesome图·DFS·traversal

LeetCode 题解工作台

重新安排行程

给你一份航线列表 tickets ，其中 tickets[i] = [from i , to i ] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。所有这些机票都属于一个从 JFK （肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返…

深度优先搜索图欧拉回路

题目描述

给你一份航线列表 tickets ，其中 tickets[i] = [from_i, to_i] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。

所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。

例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。

假定所有机票至少存在一种合理的行程。且所有的机票必须都用一次且只能用一次。

示例 1：

输入：tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
输出：["JFK","MUC","LHR","SFO","SJC"]

示例 2：

输入：tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出：["JFK","ATL","JFK","SFO","ATL","SFO"]
解释：另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"] ，但是它字典排序更大更靠后。

提示：

1 <= tickets.length <= 300
tickets[i].length == 2
from_i.length == 3
to_i.length == 3
from_i 和 to_i 由大写英文字母组成
from_i != to_i

lightbulb

解题思路

方法一：欧拉路径

题目实际上是给定 $n$ 个点和 $m$ 条边，要求从指定的起点出发，经过所有的边恰好一次，使得路径字典序最小。这是一个典型的欧拉路径问题。

由于本题保证了至少存在一种合理的行程，因此，我们直接利用 Hierholzer 算法，输出从起点出发的欧拉路径即可。

时间复杂度 $O(m \times \log m)$ ，空间复杂度 $O(m)$ 。其中 $m$ 是边的数量。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        def dfs(f: str):
            while g[f]:
                dfs(g[f].pop())
            ans.append(f)

        g = defaultdict(list)
        for f, t in sorted(tickets, reverse=True):
            g[f].append(t)
        ans = []
        dfs("JFK")
        return ans[::-1]

speed

复杂度分析

指标	值
时间	complexity is O(E log E) due to sorting adjacency lists, and space complexity is O(V + E) for the graph and recursive call stack, where V is airports and E is tickets.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate identifies graph representation with adjacency lists.
question_mark
Candidate sorts destinations to handle lexical order correctly.
question_mark
Candidate uses DFS and recognizes Eulerian path formation with backtracking.

warning

常见陷阱

外企场景

error
Failing to sort adjacency lists leading to incorrect lexical order.
error
Not removing edges after visiting, causing repeated use of the same ticket.
error
Appending instead of prepending during backtracking, yielding reversed itinerary.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allowing multiple starting airports instead of fixed 'JFK'.
arrow_right_alt
Returning all possible valid itineraries instead of just the smallest lexical order.
arrow_right_alt
Using BFS instead of DFS for traversal with priority queue for lexical order.

help

常见问题

外企场景

继续练习

#753 破解保险箱 #329 矩阵中的最长递增路径 #310 最小高度树