332_Reconstruct_Itinerary.java

classSolution {
publicList<String> findItinerary(List<List<String>> tickets) {
if (tickets == null || tickets.size() == 0) {
returnCollections.emptyList();
 }

LinkedList<String> result = newLinkedList<>();
Map<String, PriorityQueue<String>> graph = newHashMap<>();

for (List<String> t : tickets) {
graph.putIfAbsent(t.get(0), newPriorityQueue<>());
graph.get(t.get(0)).add(t.get(1));
 }

dfs("JFK", graph, result);

returnresult;
 }

privatevoiddfs(Stringdeparture, Map<String, PriorityQueue<String>> graph, LinkedList<String> path) {
PriorityQueue<String> arrivals = graph.get(departure);

while (arrivals != null && !arrivals.isEmpty()) {
dfs(arrivals.poll(), graph, path);
 }

path.addFirst(departure);
 }
}