# 332. Reconstruct Itinerary

Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.

Note:
If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary [“JFK”, “LGA”] has a smaller lexical order than [“JFK”, “LGB”].
All airports are represented by three capital letters (IATA code).
You may assume all tickets form at least one valid itinerary.
Example 1:
tickets = [[“MUC”, “LHR”], [“JFK”, “MUC”], [“SFO”, “SJC”], [“LHR”, “SFO”]]
Return [“JFK”, “MUC”, “LHR”, “SFO”, “SJC”].
Example 2:
tickets = [[“JFK”,”SFO”],[“JFK”,”ATL”],[“SFO”,”ATL”],[“ATL”,”JFK”],[“ATL”,”SFO”]]
Return [“JFK”,”ATL”,”JFK”,”SFO”,”ATL”,”SFO”].
Another possible reconstruction is [“JFK”,”SFO”,”ATL”,”JFK”,”ATL”,”SFO”]. But it is larger in lexical order.

Recursion version:

``````public void dfs(String departure, Map<String, PriorityQueue<String>> graph, List<String> result) {
//深度優先搜尋，搜尋到一個城市只是arrival city的時候（即沒有出度的時候，把這個city記入list中去，因為它肯定是最後到達的城市，然後依次向前類推
PriorityQueue<String> arrivals = graph.get(departure);
while (arrivals != null && !arrivals.isEmpty()) {
dfs(arrivals.poll(), graph, result);
}
}
public List<String> findItinerary(String[][] tickets) {
List<String> result = new ArrayList<String>();
//lexical order的要求在存入graph的時候就用priority queue先存好
Map<String, PriorityQueue<String>> graph = new HashMap<>();
for (String[] iter : tickets) {
graph.putIfAbsent(iter[0], new PriorityQueue<String>());
}
dfs("JFK", graph, result);
return result;
}``````

Stack version:

``````public List<String> findItinerary(String[][] tickets) {
List<String> result = new ArrayList<String>();
Map<String, PriorityQueue<String>> graph = new HashMap();
for (String[] iter : tickets) {
graph.putIfAbsent(iter[0], new PriorityQueue<String>());