332 Reconstruct Itinerary

Take it seriously !!!

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 fromJFK. Thus, the itinerary must begin withJFK.

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:
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.

class Solution {
    Map<String, PriorityQueue<String>> map;

    List<String> ans;
    public List<String> findItinerary(String[][] tickets) {
        map = new HashMap<>();
        ans = new LinkedList<>();
        if (tickets == null || tickets.length == 0 ) {
            return ans;
        }
        for (String[] ticket : tickets) {
            if (map.containsKey(ticket[0])) {
                map.get(ticket[0]).add(ticket[1]);
            }else {
                map.put(ticket[0], new PriorityQueue<String>());
                map.get(ticket[0]).add(ticket[1]);
            }
        }
        helper("JFK");
        return ans;
    }
    public void helper (String depart) {
        while (map.containsKey(depart) && !map.get(depart).isEmpty()) {
            helper(map.get(depart).poll());
        }
        ans.add(0, depart);
    }
}