力扣 332 重新安排行程

题意：给一组机票，重新构建行程

思路：

1. 用map记录每一个出发的城市和它能到达的城市，并用pq来给到达的城市从小到大排序
2. DFS，每次获取当前城市能到达的城市
3. 如果它能到达的城市为空，则把它加入结果
4. 否则遍历它能到达的城市，并对每一个城市DFS
5. 把当前城市加入结果
6. 倒序的结果即为所求

思想：DFS

复杂度：时间O（n)，空间O(n)

class Solution {
    public List<String> findItinerary(List<List<String>> tickets) {
        HashMap<String, PriorityQueue<String>> map = new HashMap();
        for(List<String> ticket: tickets) {
            if(map.containsKey(ticket.get(0))) {
                map.get(ticket.get(0)).add(ticket.get(1));
            } else {
                PriorityQueue<String> temp = new PriorityQueue<String>();
                temp.add(ticket.get(1));
                map.put(ticket.get(0), temp);
            }
        }
        List<String> result = new ArrayList();
        build("JFK", map, result);
        Collections.reverse(result);
        return result;    
    }
    
    void build(String from, HashMap<String, PriorityQueue<String>> map, List<String> res) {
        PriorityQueue<String> cur = map.get(from);
        while(cur!= null && !cur.isEmpty()) {
            String nfrom = cur.poll();
            build(nfrom, map, res);
        }
        res.add(from);
    }
}