332. 重新安排行程

给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。

所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。

• 例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。

假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。

示例 1：

输入：tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
输出：["JFK","MUC","LHR","SFO","SJC"]

示例 2：

输入：tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出：["JFK","ATL","JFK","SFO","ATL","SFO"]
解释：另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"] ，但是它字典排序更大更靠后。

提示：

• 1 <= tickets.length <= 300
• tickets[i].length == 2
• fromi.length == 3
• toi.length == 3
• fromi 和 toi 由大写英文字母组成
• fromi != toi

思路

这道题目有几个难点：

1. 一个行程中，如果航班处理不好容易变成一个圈，成为死循环
2. 有多种解法，字母序靠前排在前面，让很多同学望而退步，如何该记录映射关系呢 ？
3. 使用回溯法（也可以说深搜） 的话，那么终止条件是什么呢？
4. 搜索的过程中，如何遍历一个机场所对应的所有机场。
5. 同一行程的机票可以有多张

如何理解死循环

对于死循环，我来举一个有重复机场的例子：

为什么要举这个例子呢，就是告诉大家，出发机场和到达机场也会重复的，如果在解题的过程中没有对集合元素处理好，就会死循环。

该记录映射关系

有多种解法，字母序靠前排在前面，让很多同学望而退步，如何该记录映射关系呢 ？

一个机场映射多个机场，机场之间要靠字母序排列，一个机场映射多个机场，可以使用 HashMap，组装成 Map<出发机场, 到达机场的集合> 这样的形式。如果让多个机场之间再有顺序的话，可以使用 List 或者TreeMap，这样存放映射关系可以定义为 Map<出发机场, List<到达机场>> 或者 Map<出发机场, TreeMap<到达机场, 机票数量>> 。如果使用 List 的话每到达一个机场就要把该机票从 List 中 Remove 掉，这样比较耗费资源，如果使用 TreeMap 的话只需要让机票数量减一即可。如果“航班次数”大于零，说明目的地还可以飞，如果如果“航班次数”等于零说明目的地不能飞了，而不用对集合做删除元素或者增加元素的操作。

回溯法

这道题目我使用回溯法，那么下面按照我总结的回溯模板来：

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

本题以输入：[[“JFK”, “KUL”], [“JFK”, “NRT”], [“NRT”, “JFK”]为例，抽象为树形结构如下：

「如果需要搜索整颗二叉树，那么递归函数就不要返回值，如果要搜索其中一条符合条件的路径，递归函数就需要返回值，因为遇到符合条件的路径了就要及时返回。」

因为我们只需要找到一个行程，就是在树形结构中唯一的一条通向叶子节点的路线，所以找到了这个叶子节点了直接返回，所以这里函数返回值用的是bool

解法

class Solution {

    List<String> result = new ArrayList<>();

    public List<String> findItinerary(List<List<String>> tickets) {
        if (tickets == null || tickets.size() == 0) {
            return result;
        }
        result.add("JFK");
        //Map<出发点，Map<降落点, 机票数量>>
        Map<String, TreeMap<String, Integer>> map = new HashMap<>();
        for (List<String> ticket : tickets) {
            //使用TreeMap对降落点进行排序
            TreeMap<String, Integer> arriveMap = map.getOrDefault(ticket.get(0), new TreeMap<>());
            arriveMap.put(ticket.get(1), arriveMap.getOrDefault(ticket.get(1), 0) + 1);
            map.put(ticket.get(0), arriveMap);
        }
        findNext(map, "JFK", tickets.size());
        return result;
    }

    public boolean findNext(Map<String, TreeMap<String, Integer>> map, String start, int ticketNum) {
        if (result.size() == ticketNum + 1) {
            //已使用完所有机票
            return true;
        }
        Map<String, Integer> arriveMap = map.get(start);
        if (arriveMap != null) {
            for (Map.Entry<String, Integer> entry : arriveMap.entrySet()) {
                int count = entry.getValue();
                String end = entry.getKey();
                //飞往该降落点已无机票可用
                if (count == 0) {
                    continue;
                }
                result.add(end);
                arriveMap.put(end, count - 1);
                if (findNext(map, end, ticketNum)) {
                    return true;
                }
                //撤销选择
                result.remove(result.size() - 1);
                arriveMap.put(end, count);
            }
        }
        //未使用完所有机票便走到了叶子节点
        return false;
    }
}