### 题目

Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.

Note:

• If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].
• All airports are represented by three capital letters (IATA code).
• You may assume all tickets form at least one valid itinerary.

Example 1:

tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Return ["JFK", "MUC", "LHR", "SFO", "SJC"].


Example 2:

tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Return ["JFK","ATL","JFK","SFO","ATL","SFO"].
Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical order.


### 利用回溯算法做DFS探索

#### 代码

class Solution {
public List<String> findItinerary(String[][] tickets) {
Map<String,List<String>> map = getMap(tickets);
return dfs(map,"JFK");
}
private Map<String,List<String>> getMap(String[][] tickets) {
Map<String,List<String>> map = new HashMap<>();
for (String[] ticket : tickets) {
if (map.containsKey(ticket[0])) {
} else {
map.put(ticket[0],new ArrayList<String>(Arrays.asList(new String[]{ticket[1]})));
}
}
for (Map.Entry<String,List<String>> entry : map.entrySet()) {
Collections.sort(entry.getValue());
}
return map;
}
private List<String> dfs(Map<String,List<String>> map, String from) {
if (map.isEmpty()) {
return new ArrayList<String>(Arrays.asList(new String[]{from}));
}
List<String> destinies = map.get(from);
if (destinies == null) { return null; }
for (int i = 0; i < destinies.size(); i++) {
String to = destinies.remove(i);
if (destinies.isEmpty()) {
map.remove(from);
}
List<String> subItinerary = dfs(map,to);
if (subItinerary != null) {