仅为个人记录复盘学习历程，解题思路来自代码随想录
代码随想录刷题笔记总结网址:
代码随想录
332.重新安排行程
给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。
如果存在多种有效的行程，请你按字符自然排序返回最小的行程组合。例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前
所有的机场都用三个大写字母表示（机场代码）。
假定所有机票至少存在一种合理的行程。
所有的机票必须都用一次 且 只能用一次。
提供参数：二维字符数组List<List<String>>tickets。
主要操作：
递归三要素
1.返回值类型和输入参数：
使用全局变量path记录单个结果，输入参数tickets，用于判断是否使用过的used数组。
找到一条数据即可返回，返回值类型为boolean。
2.终止条件：
当path.size()==tickets+1时，说明找到一条合适的路径，返回。
3.单层递归逻辑：
使用for循环横向遍历解空间树，进行判断：
如果当前节点未使用过，且满足可以由路径上的最后一个节点到达，则满足条件。
将该结点加入path，递归纵向遍历解空间树，递归结束后回溯，如果递归返回结果为true，则直接返回true。
代码大致如下（正确但不能通过leetcode，但是感觉思路看上去更加符合回溯）：
private List<String>res;private List<String>path;public List<String> findItinerary(List<List<String>> tickets) {Collections.sort(tickets,(a,b)->a.get(1).compareTo(b.get(1)));path=new ArrayList<>();boolean[]used=new boolean[tickets.size()];path.add("JFK");backTrace(tickets,used);return res;}public boolean backTrace(List<List<String>>tickets,boolean[]used){//终止条件if(path.size()==tickets.size()+1){res=new ArrayList(path);return true;}for(int i=0;i<tickets.size();i++){if(!used[i]&&tickets.get(i).get(0).equals(path.get((path.size()-1)))){path.add(tickets.get(i).get(1));used[i]=true;if(backTrace(tickets,used))return true;used[i]=false;path.remove(path.size()-1);}}return false;} 能通过leetcode的另一种方法：
private Map<String,Map<String,Integer>>map;private List<String>path;public List<String> findItinerary(List<List<String>> tickets) {//初始化数据map=new HashMap<String,Map<String,Integer>>();path=new ArrayList<>();//初始化映射关系for(List<String>ticket:tickets){//定义临时变量Map<String,Integer>temp;//如果map中已经有键为ticket中出发地的键值对if(map.containsKey(ticket.get(0))){//将在map中键为ticket.get(0)的值（一个Map<String,Integer>的键值对）返回给temptemp=map.get(ticket.get(0));//在temp中更新或加入数据，如果temp中有以ticket.get(1)为键的值，则获取它的value并加1//否则将ticket.get(1)加入，默认值为0并加1temp.put(ticket.get(1),temp.getOrDefault(ticket.get(1),0)+1);}else{temp=new TreeMap<>();temp.put(ticket.get(1),1);}map.put(ticket.get(0),temp);}path.add("JFK");backTrace(tickets.size());return new ArrayList(path);}public boolean backTrace(int ticketNum){//1终止条件if(path.size()==ticketNum+1){return true;}//2.单层递归逻辑//2.1获取当前路径最后一个元素作为起点String last=path.get(path.size()-1);//map.get(last).entrySet(),获取键为last的值的集合//Map<StringInteger>temp代表的是每个键为last的值if(map.containsKey(last)){for(Map.Entry<String,Integer>temp:map.get(last).entrySet()){//获取值的出现次数int count=temp.getValue();if(count>0){path.add(temp.getKey());temp.setValue(count-1);if(backTrace(ticketNum))return true;temp.setValue(count);path.remove(path.size()-1);}}}return false;}