# Reconstruct Itinerary Leetcode

#1

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:

1. 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"]`.
2. All airports are represented by three capital letters (IATA code).
3. You may assume all tickets form at least one valid itinerary.

Example 1:

````Input: ``[["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]`
Output: `["JFK", "MUC", "LHR", "SFO", "SJC"]`
```

Example 2:

````Input: ``[["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]`
Output: `["JFK","ATL","JFK","SFO","ATL","SFO"]`
Explanation: Another possible reconstruction is `["JFK","SFO","ATL","JFK","ATL","SFO"]`.
But it is larger in lexical order.
```

#2

The below code uses Hierholzer’s Algorithm to visit all nodes(destinations) exactly once.

``````class Solution {

HashMap<String,PriorityQueue<String>> map=new HashMap<>();

public List<String> findItinerary(String[][] tickets) {
for(String[] ticket:tickets)
{
if(!map.containsKey(ticket[0]))
{
map.put(ticket[0],new PriorityQueue<String>());
}
map.get(ticket[0]).offer(ticket[1]);
}
helper("JFK");
return result;
}

private void helper(String ticket){
PriorityQueue<String> arrivals = map.get(ticket);
while(arrivals!=null && arrivals.size()>0){
helper(arrivals.poll());
}