给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 出发。

说明:

1，如果存在多种有效的行程，你可以按字符自然排序返回最小的行程组合。例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前

2，所有的机场都用三个大写字母表示（机场代码）。

3，假定所有机票至少存在一种合理的行程。

示例 1:

输入: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
输出: ["JFK", "MUC", "LHR", "SFO", "SJC"]

示例 2:

输入: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]

输出: ["JFK","ATL","JFK","SFO","ATL","SFO"]

解释: 另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"]。但是它自然排序更大更靠后。

答案：

 1public List<String> findItinerary(List<List<String>> tickets) {
 2    LinkedList<String> ret = new LinkedList<>();
 3    Map<String, PriorityQueue<String>> map = new HashMap<>();
 4    Stack<String> stack = new Stack<>();
 5    for (int i = 0; i < tickets.size(); i++) {
 6        if (!map.containsKey(tickets.get(i).get(0)))
 7            map.put(tickets.get(i).get(0), new PriorityQueue<>());
 8        map.get(tickets.get(i).get(0)).offer(tickets.get(i).get(1));
 9    }
10    stack.push("JFK");
11    while (!stack.isEmpty()) {
12        String next = stack.peek();
13        if (map.containsKey(next) && map.get(next).size() > 0)
14            stack.push(map.get(next).poll());
15        else
16            ret.addFirst(stack.pop());
17    }
18    return ret;
19}

解析：

第5到9行会对同一出发地到不同的目的地进行排序，第14行表示还有目的地可去，一个出发地可能会有多个目的地，第16行表示当前的出发地没有目的地可去了，注意这里的第16行addFirst是加入到队列的前面，因为stack是个先进后出的栈。当然我们还可以使用递归的方式

 1public List<String> findItinerary(List<List<String>> tickets) {
 2    Map<String, PriorityQueue<String>> flights = new HashMap<>();
 3    LinkedList<String> path = new LinkedList<>();
 4    for (int i = 0; i < tickets.size(); i++) {
 5        flights.putIfAbsent(tickets.get(i).get(0), new PriorityQueue<>());
 6        flights.get(tickets.get(i).get(0)).add(tickets.get(i).get(1));
 7    }
 8    dfs("JFK", flights, path);
 9    return path;
10}
11
12public void dfs(String departure, Map<String, PriorityQueue<String>> flights, LinkedList<String> path) {
13    PriorityQueue<String> arrivals = flights.get(departure);
14    while (arrivals != null && !arrivals.isEmpty())
15        dfs(arrivals.poll(), flights, path);
16    path.addFirst(departure);
17}