思路:本题使用回溯解决的难点,首先在于如何处理提供的目的机场和到达机场的关系,因为首先要有对应的映射关系,才能遍历一个机场对应的所有机场,所以应当采用map的方式来记录映射,k-v分别是出发机场,(目的机场,航班数量),在进行回溯之前应该首先先对题目提供的tickets进行处理 用map记录其映射关系.之后再写回溯部分函数的时候要注意回溯的终止条件可以通过返回集的长度来判断,同时再进行回溯的时候要确保当前出发机场的航班数量要大于0,每走完一条线航班数量就会减一,只有在大于0的情况下,出发机场才可以飞,这样可以防止死循环的发生(因为出发机场和目的机场是可以重复的)

class Solution {
    LinkedList<String> res;;
    private Map<String, Map<String, Integer>> map;
    public List<String> findItinerary(List<List<String>> tickets) {
        // 用map记录 出发机场 对应的目的机场和航班的数量
        map = new HashMap<String, Map<String,Integer>>();
        res = new LinkedList<>();
        // 从tickets中获取单张的机票 将其映射关系记录到map中
        for (List<String> t : tickets){
            // 用temp帮助处理和更新映射的值
            Map<String,Integer> temp;
            // 判断map中是否存在当前的出发机场
            if (map.containsKey(t.get(0))){
                // 在存在的情况下 用temp获取当前机场对应的目的机场和航班的数量
                temp = map.get(t.get(0));
                // 通过当前机票对应的目的机场 更新temp中的目的机场的航班的数量.
                temp.put(t.get(1), temp.getOrDefault(t.get(1),0) + 1);
            }else {
//                TreeMap默认按照升序排列，符合按照字典排列的最小要求
                temp = new TreeMap<>();
                // 如果不存在机票中的目的机场 就创建一个赋值为1
                temp.put(t.get(1),1);
            }
            // 把temp更新到map中
            map.put(t.get(0),temp);
        }
        res.add("JFK");
        backTracking(tickets.size());
        return new ArrayList<>(res);
    }
    public boolean backTracking(int ticketsNum){
        // res大小为所以机票数加1说明已经完整的走了一圈
        if(res.size() == ticketsNum + 1) return true;
        String resLast = res.getLast();
        // 防止null
        if (map.containsKey(resLast)){
            // 获取当前处理机场的 目的机场和航班数量
            for (Map.Entry<String,Integer> ticket : map.get(resLast).entrySet()){
                int count = ticket.getValue();
//仅在当前目的机场还有航班的时候才进行回溯
                if (count > 0){
                    res.add(ticket.getKey());
                    ticket.setValue(count - 1);
                    if (backTracking(ticketsNum)) return true;
                    res.removeLast();
                    ticket.setValue(count);
                }
            }
        }
        return false;
    }
}