Cacher is the code snippet organizer for pro developers

public class Solution {
    public List<String> findItinerary(String[][] tickets) {
        List<String> result = new ArrayList();
        if (tickets == null || tickets.length == 0) return result;
        
        Map<String, TreeMap<String, Integer>> map = new HashMap();
        
        for (String[] pair : tickets) {
            if (!map.containsKey(pair[0])) map.put(pair[0], new TreeMap());
            TreeMap<String, Integer> cache = map.get(pair[0]);
            cache.put(pair[1], cache.containsKey(pair[1]) ? cache.get(pair[1]) + 1 : 1);
        }
        dfs("JFK", map, result, tickets.length + 1);
        return result;
    }
    
    private boolean dfs(String curr, Map<String, TreeMap<String, Integer>> map, List<String> result, int size) {
        result.add(curr);
        if (result.size() == size) return true;
        if (map.containsKey(curr)) {
            TreeMap<String, Integer> children = map.get(curr);

            for (String next : children.keySet()) {
                if (children.get(next) > 0) {
                    children.put(next, children.get(next) - 1);
                    boolean res = dfs(next, map, result, size);
                    if (res) return true;
                    children.put(next, children.get(next) + 1);
                }
            }
        }
        result.remove(result.size() - 1);
        return false;
    }
}

 public List<String> findItinerary(String[][] tickets) {
        List<String> ans = new ArrayList<String>();
        if(tickets == null || tickets.length == 0) return ans;
        Map<String, PriorityQueue<String>> ticketsMap = new HashMap<>();
        for(int i = 0; i < tickets.length; i++) {
            if(!ticketsMap.containsKey(tickets[i][0])) ticketsMap.put(tickets[i][0], new PriorityQueue<String>());
            ticketsMap.get(tickets[i][0]).add(tickets[i][1]);
        }

        String curr = "JFK";
        Stack<String> drawBack = new Stack<String>();
        for(int i = 0; i < tickets.length; i++) {
            while(!ticketsMap.containsKey(curr) || ticketsMap.get(curr).isEmpty()) {
                drawBack.push(curr);
                curr = ans.remove(ans.size()-1);
            }
            ans.add(curr);
            curr = ticketsMap.get(curr).poll();
        }
        ans.add(curr);
        while(!drawBack.isEmpty()) ans.add(drawBack.pop());
        return ans;
    }

public class Solution {

    Map<String, PriorityQueue<String>> flights;
    LinkedList<String> path;

    public List<String> findItinerary(String[][] tickets) {
        flights = new HashMap<>();
        path = new LinkedList<>();
        for (String[] ticket : tickets) {
            flights.putIfAbsent(ticket[0], new PriorityQueue<>());
            flights.get(ticket[0]).add(ticket[1]);
        }
        dfs("JFK");
        return path;
    }

    public void dfs(String departure) {
        PriorityQueue<String> arrivals = flights.get(departure);
        while (arrivals != null && !arrivals.isEmpty())
            dfs(arrivals.poll());
        path.addFirst(departure);
    }
}

79 / 79 test cases passed.
Status: Accepted
Runtime: 11 ms

/*
[["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]]
Expected Answer :
["JFK","NRT","JFK","KUL"]
*/

public class Solution {
    

    public List<String> findItinerary(String[][] tickets) {
        Map<String, List<String>> graph = new HashMap<>();
        // record the edges we have visited
        Map<String, boolean[]> visited = new HashMap<>();
        for (String[] t : tickets) {
            if (!graph.containsKey(t[0])) {
                graph.put(t[0], new ArrayList<>());
            }
            graph.get(t[0]).add(t[1]);
        }
        for (String key : graph.keySet()) {
            Collections.sort(graph.get(key));
            visited.put(key, new boolean[graph.get(key).size()]);
        }
        
        int n = tickets.length + 1;
  
        List<String> path = new ArrayList<>();
        search("JFK", graph, n, path, visited);
        return path;
    }
    
    // backtrack
    private boolean search(String cur, Map<String, List<String>> graph, int n, List<String> path, Map<String, boolean[]> visited) {
        path.add(cur);
        // reach last level
        if (path.size() == n) {
            return true;
        }
        List<String> arrivals = graph.get(cur);
        if (arrivals == null) {
            path.remove(path.size() - 1);
            return false;
        };
        for (int i = 0; i < arrivals.size(); i++) {
            String arrival = arrivals.get(i);
            if (visited.get(cur)[i]) continue;
            visited.get(cur)[i] = true;
            if (search(arrival, graph, n, path, visited)) return true;
            visited.get(cur)[i] = false;
        }
        path.remove(path.size() - 1);
        return false;
        
    }
    
}