332 Reconstruct Itinerary **** New and Medium

[["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]

Your answer

["SJC","SFO","LHR","MUC","JFK"]

Expected answer

["JFK","MUC","LHR","SFO","SJC"]

• [x] 这个部分非常的关键：你只能用LINKEDLIST存储你的结果，因为你用的DFS，所以最先被加到LIST里面的一定是最终目的地， 而起点反而是最后加进来的，所以你得array.ADD(index, num)

• [x] 还有一点要注意的，就是你在从JFK开始往下遍历得的时候

得用一个WHILE 循环，因为JFK下可能有很多选择，你得找一个LEXICAL order最小的先开始，所以用了pq

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.

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

Input: tickets = [["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.

Input:
[["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]]
Output:
["JFK","KUL"]
Expected:
["JFK","NRT","JFK","KUL"]

这个例子非常重要！！！！这是是用WHILE 的必要性！！！

class Solution {
    Map<String, PriorityQueue<String>> map;
    List<String> ans;
    int index  = 0;
    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.put(ticket[0], new PriorityQueue<>()); 
            }
            map.get(ticket[0]).offer(ticket[1]);
        }
        helper("JFK");
        return ans;
    }
    public void helper(String depart) {
        while  (map.containsKey(depart) && (!map.get(depart).isEmpty())) {
            String pow = map.get(depart).poll();
            System.out.println("pow" + pow);
           helper(pow);
       }
        System.out.println("index: " + index + " depart " + depart);
        index++;
        ans.add(0, depart);

    }
}