332.Reconstruct Itinerary

区分边的遍历和点的遍历

I am pretty sure that Eulerian graph means visit each “EDGE” once and only once.

The one that visited each node once and only once is called Hamiltonian.

Hard!!!

class Solution {
    public List<String> findItinerary(String[][] tickets) {
        Map<String, PriorityQueue<String>> map = new HashMap<>();
        for(int i = 0; i < tickets.length; i++){
            String start = tickets[i][0];
            String end = tickets[i][1];
            PriorityQueue<String> queue = map.getOrDefault(start, new PriorityQueue<String>());
            queue.offer(end);
            map.put(start, queue);
        }
        List<String> ans = new LinkedList<>();
        dfs(map, ans, "JFK");
        return ans;
    }
    public void dfs(Map<String, PriorityQueue<String>> map, List<String> ans,  String start){
        while(map.containsKey(start) && !map.get(start).isEmpty()){
            dfs(map, ans, map.get(start).poll());
        }
        ans.add(0, start);
    }
}