loading

Reconstruct Itinerary — Step-by-Step Visualization

hardLeetCode #332GraphDFSEulerian Path

You are given a list of airline tickets where `tickets[i] = [from_i, to_i]` represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it. All of the tickets belong to a man who departs from 'JFK'. Thus, the itinerary must begin with 'JFK'. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string.

Algorithm Pattern

Hierholzer's Algorithm (Eulerian Path)

Key Idea

This is a problem of finding an Eulerian path in a directed graph. We use DFS to traverse the graph. To ensure the smallest lexical order, we sort the neighbors of each airport alphabetically. The core of Hierholzer's algorithm is that we only add a node to the itinerary *after* we've visited all its outgoing edges. This naturally handles dead ends and returns the path in reverse order.

Step-by-Step Approach

  1. Build an adjacency list where each key is a departure airport and the value is a min-priority queue (or sorted list) of arrival airports.
  2. Start a DFS from 'JFK'.
  3. In the DFS, while the current airport still has outgoing tickets, pick the alphabetically smallest destination and recursively call DFS on it.
  4. After all outgoing tickets from the current airport are used, append the airport to the result list.
  5. The final result will be the reverse of the collected airports.

Common Gotchas

  • The 'post-order' recording (adding to result *after* recursion) is what makes the algorithm correct for Eulerian paths.
  • Make sure to remove tickets as you use them.

Related Problems

← All problems