243. Reconstruct Itinerary — Eulerian Path

Hard · Depth-First Search

Given a list of airline tickets [from, to], reconstruct the itinerary in order starting from "JFK". All tickets must be used exactly once. If multiple valid itineraries exist, return the lexicographically smallest one.

Examples

Example 1
Input: tickets=[["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output: ["JFK","MUC","LHR","SFO","SJC"]

Constraints