题目

给你一份航线列表 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

思路

这道题目还是很难的，之前我们用回溯法解决了如下问题：组合问题，分割问题，子集问题，排列问题。

直觉上来看这道题和回溯法没有什么关系，更像是图论中的深度优先搜索。

实际上确实是深搜，但这是深搜中使用了回溯的例子，在查找路径的时候，如果不回溯，怎么能查到目标路径呢。

所以我倾向于说本题应该使用回溯法，那么我也用回溯法的思路来讲解本题，其实深搜一般都使用了回溯法的思路，在图论系列中我会再详细讲解深搜。

这道题目有几个难点：

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

如何理解死循环

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

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

该如何记录映射关系

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

一个机场映射多个机场，机场之间要靠字母序排列，可以考虑使用 TreeMap 或 TreeSet 。

这样存放映射关系可以定义为 TreeMap> targets 或者 TreeMap> targets。
含义如下：

TreeMap> targets：TreeMap<出发机场, 到达机场的集合> targets
TreeMap> targets：TreeMap<出发机场, TreeMap<到达机场, 航班次数>> targets

这两个结构，我选择了后者，因为如果使用 TreeMap> targets 遍历 TreeSet 的时候，不能删除元素，一旦删除元素，迭代器就失效了。

再说一下为什么一定要增删元素呢，正如开篇我给出的图中所示，出发机场和到达机场是会重复的，搜索的过程没及时删除目的机场就会死循环。

所以搜索的过程中就是要不断的删 TreeSet 里的元素，所以我推荐使用 TreeMap> targets 。

在遍历 TreeMap<出发机场, TreeMap<到达机场, 航班次数>> targets 的过程中，可以使用”航班次数”这个字段的数字做相应的增减，来标记到达机场是否使用过了。

如果“航班次数”大于零，说明目的地还可以飞，如果如果“航班次数”等于零说明目的地不能飞了，而不用对集合做删除元素或者增加元素的操作。

相当于说我不删，我就做一个标记。

回溯法三部曲

按照模板：

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

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

1、递归函数参数

在讲解映射关系的时候，已经讲过了，使用 TreeMap> targets 来记录航班的映射关系，我定义为全局变量。
当然把参数放进函数里传进去也是可以的，我是尽量控制函数里参数的长度。

参数里还需要 ticketCount ，表示有多少个航班（终止条件会用上）。

代码如下：

LinkedList<String> result = new LinkedList<>();
// <出发机场,   <到达机场,航班次数 >>
Map<String, Map<String, Integer>> map = new HashMap<>();
// 总计几个航班
int ticketCount = 0;

boolean backTracking()

注意函数返回值我用的是 boolean ！

我们之前讲解回溯算法的时候，一般函数返回值都是 void ，这次为什么是 boolean 呢？

因为我们只需要找到一个行程，就是在树形结构中唯一的一条通向叶子节点的路线，如图：

所以找到了这个叶子节点了直接返回。

当然本题的 targets 和 result 都需要初始化，代码如下：

// 循环取出机票，建立 from->to 的映射关系，初始化 map
for (List<String> ticket : tickets) {
    // 取出一张票 -> ticket(from,to) -> ticket[0]=from, ticket[1]=to
    String from = ticket.get(0);
    String to = ticket.get(1);

    Map<String, Integer> tmpMap;

    // 若 map 中含有该票的出发机场 -> from
    if (map.containsKey(from)) {
        // map 中含有该票的出发机场 -> from

        // 获取从该机场出发的所有可达机场及其航班次数
        tmpMap = map.get(from);
        // 更新数据【从该机场出发的所有可达机场及其航班次数】，因为本轮循环取到了一张票，所以需要对此数据做更新
        tmpMap.put(to, tmpMap.getOrDefault(to, 0) + 1);
    } else {
        // map 中不含有该票的出发机场 -> from

        // TreeMap 默认将保存的数据根据 key 进行升序排序
        tmpMap = new TreeMap<>();
        tmpMap.put(to, 1);
    }

    map.put(from, tmpMap);
}

// 总计有几张机票
this.ticketCount = tickets.size();

// 题目规定, 行程必须从 JFK 开始
result.add("JFK");

2、递归终止条件

拿题目中的示例为例，输入: [[“MUC”, “LHR”], [“JFK”, “MUC”], [“SFO”, “SJC”], [“LHR”, “SFO”]] ，这是有4个航班，那么只要找出一种行程，行程里的机场个数是5就可以了。

所以终止条件是：我们回溯遍历的过程中，遇到的机场个数，如果达到了（航班数量+1），那么我们就找到了一个行程，把所有航班串在一起了。

代码如下：

if (result.size() == ticketCount + 1) {
    return true;
}

已经看习惯回溯法代码的同学，到叶子节点了习惯性的想要收集结果，但发现并不需要，本题的result相当于 216. 组合总和III 中的 path ，也就是本题的 result 就是记录路径的（就一条），在如下单层搜索的逻辑中 result 就添加元素了。

3、单层搜索的逻辑

回溯的过程中，如何遍历一个机场所对应的所有机场呢？

这里刚刚说过，在选择映射函数的时候，不能选择 TreeMap> targets ，因为一旦有元素增删，迭代器就会失效，当然可能有牛逼的容器删除元素迭代器不会失效，这里就不在讨论了。

所以我选择了 TreeMap> targets 来做机场之间的映射。

遍历过程如下：

for (Map.Entry<String, Integer> target : map.get(from).entrySet()) {
    // 获取航班次数
    int count = target.getValue();
    // 若航班次数大于 0
    if (count > 0) {
        // 飞往该目标机场
        result.add(target.getKey());
        target.setValue(count - 1);

        // 飞往下一站
        if (backTracking()) return true;

        // 回溯
        result.removeLast();
        target.setValue(count);
    }
}

可以看出通过 TreeMap> targets 里的 int 字段来判断这个集合里的机场是否使用过，这样避免了直接去删元素。

分析完毕。

总结

本题其实可以算是一道hard的题目了，关于本题的难点我在文中已经列出了。

如果单纯的回溯搜索（深搜）并不难，难还难在容器的选择和使用上。

本题其实是一道深度优先搜索的题目，但是我完全使用回溯法的思路来讲解这道题题目，算是给大家拓展一下思维方式，其实深搜和回溯也是分不开的，毕竟最终都是用递归。

如果最终代码，发现照着回溯法模板画的话好像也能画出来，但难就难如何知道可以使用回溯，以及如果套进去，所以我再写了这么长的一篇来详细讲解。

答案

Java

class Solution {
    LinkedList<String> result = new LinkedList<>();
    // <出发机场,   <到达机场,航班次数 >>
    Map<String, Map<String, Integer>> map = new HashMap<>();
    // 总计几张机票
    int ticketCount = 0;

    public List<String> findItinerary(List<List<String>> tickets) {
        // 循环取出机票，建立 from->to 的映射关系，初始化 map
        for (List<String> ticket : tickets) {
            // 取出一张票 -> ticket(from,to) -> ticket[0]=from, ticket[1]=to
            String from = ticket.get(0);
            String to = ticket.get(1);

            Map<String, Integer> tmpMap;

            // 若 map 中含有该票的出发机场 -> from
            if (map.containsKey(from)) {
                // map 中含有该票的出发机场 -> from

                // 获取从该机场出发的所有可达机场及其航班次数
                tmpMap = map.get(from);
                // 更新数据【从该机场出发的所有可达机场及其航班次数】，因为本轮循环取到了一张票，所以需要对此数据做更新
                tmpMap.put(to, tmpMap.getOrDefault(to, 0) + 1);
            } else {
                // map 中不含有该票的出发机场 -> from

                // TreeMap 默认将保存的数据根据 key 进行升序排序
                tmpMap = new TreeMap<>();
                tmpMap.put(to, 1);
            }

            map.put(from, tmpMap);
        }

        // 总计有几张机票
        this.ticketCount = tickets.size();

        // 题目规定, 行程必须从 JFK 开始
        result.add("JFK");

        // 总计航班次数 tickets.size(), 当前还剩余 tickets.size() 个航班没有飞
        System.out.println(backTracking());

        return new ArrayList<>(result);
    }

    private boolean backTracking() {
        // 遇到的机场个数，如果达到了（航班数量+1），那么我们就找到了一个行程
        if (result.size() == ticketCount + 1) {
            return true;
        }

        // 获取出发点
        String from = result.getLast();

        // 若 map 中含有该起点对应的机场数据
        if (map.containsKey(from)) {
            // 循环取出目标机场数据
            for (Map.Entry<String, Integer> target : map.get(from).entrySet()) {
                // 获取航班次数
                int count = target.getValue();
                // 若航班次数大于 0
                if (count > 0) {
                    // 飞往该目标机场
                    result.add(target.getKey());
                    target.setValue(count - 1);

                    // 飞往下一站
                    if (backTracking()) return true;

                    // 回溯
                    result.removeLast();
                    target.setValue(count);
                }
            }
        }
        return false;
    }
}

补充一下，Java 的这个测试用例是有问题的。