332.重新安排行程

题解

​ 本题的题意就是找到以JFK为起点的欧拉通路，而且需要找到字典序最小的那个结果。所以我们使用优先队列来实现，普通的队列的特点是先进先出，优先队列的特点是先弹出优先度最高的节点。但我们如果直接走字典序最小的路，可能会走到一个死胡同，无法达成使用每一张机票的目的，所以我们要把会走到死胡同的节点放到最后遍历。

​ 至于如何实现，只要该节点还没走到死胡同，就继续递归，递归不会停止。直至遇到死胡同，然后从死胡同那个节点开始入栈，再将栈内容反转即可。

class Solution {
    Map<String, PriorityQueue<String>> map = new HashMap<String, PriorityQueue<String>>();
    List<String> itinerary = new LinkedList<String>();

    public List<String> findItinerary(List<List<String>> tickets) {
        for (List<String> ticket : tickets) {
            String src = ticket.get(0), dst = ticket.get(1);
            if (!map.containsKey(src)) {
                map.put(src, new PriorityQueue<String>());
            }
            map.get(src).offer(dst);
        }
        dfs("JFK");
        Collections.reverse(itinerary);
        return itinerary;
    }

    public void dfs(String curr) {
        while (map.containsKey(curr) && map.get(curr).size() > 0) {
            String tmp = map.get(curr).poll();
            dfs(tmp);
        }
        itinerary.add(curr);
    }
}