思路

普通节点出度和入度数是相等的，在while用完之前，我有入有出，又回去了，但是最后一个节点就不一样了，其出度数必定比入度数小1，最后一次走到这，应该是入度1次，出度0次，进来了发现回不去了呀，输出了我们的第一个需要的节点，也就是终点，同理，开始节点出度比入度大1，最后别人都走完了，他还要出最后一次，出完这一次，才能输出，也就是保证最后一个添加的是起点，这时候反转就ok啦。

考虑到字典序，就需要排序啦，影响的也就是拆边的顺序，不可能影响到头尾：

1. 如果死胡同节点字典序更小，则当前直接进入死胡同。那么死胡同一定是第一个进入结果集的，满足它是一笔画最后一画的条件。你从死胡同递归出来以后，根据字典序去遍历其他的非死胡同节点。这样一定能产生一个有效的路径。
2. 如果死胡同的字典序更大，则当前递归进入其他的非死胡同节点，那么一定会再次递归回到当前节点而进入死胡同。为什么？其他节点出入度都相同，递归相当于拆边，每个节点出入边都拆相等的次数，一定会回到原点。这种情况下，死胡同仍然为第一个进入结果集的节点。

题目

题目-重新安排行程

回溯解法

class Solution {
    List<String> res = new ArrayList<>();
    List<String> path = new ArrayList<>();
    public List<String> findItinerary(List<List<String>> tickets) {
        tickets.sort((o1,o2) -> o1.get(1).compareTo(o2.get(1)));
        boolean[] ticketsUsed = new boolean[tickets.size()];
        backtracking("JFK", tickets, ticketsUsed, 0);
        path.add(0,"JFK");
        return path;
    }

    public boolean backtracking(String start, List<List<String>> tickets, boolean[] ticketsUsed, int count){
        if(count == tickets.size()){
            path = new ArrayList(res);
            return true;
        }
        for(int i = 0; i < tickets.size(); i++){
            if(!tickets.get(i).get(0).equals(start) || ticketsUsed[i]){
                continue;                
            }
            res.add(tickets.get(i).get(1));
            ticketsUsed[i] = true;
            if(backtracking(tickets.get(i).get(1), tickets, ticketsUsed, count + 1)){
                return true;
            }
            ticketsUsed[i] = false;
            res.remove(res.size() - 1);
        }
        return false;
    }
}

Hierholzer 算法

class Solution {
    List<String> res = new ArrayList<>();
    public List<String> findItinerary(List<List<String>> tickets) {
        Map<String,PriorityQueue<String>> map = buildGraph(tickets);
        dfs(map, "JFK");
        Collections.reverse(res);
        return res;

    }


    public Map<String, PriorityQueue<String>> buildGraph(List<List<String>> tickets){
        Map<String, PriorityQueue<String>> map = new HashMap<>();
        for(List<String> ticket : tickets){
            String from = ticket.get(0);
            String to = ticket.get(1);
            if(!map.containsKey(from)){
                map.put(from, new PriorityQueue<>((o1,o2) -> {
                    return o1.compareTo(o2);
                }));
            }
            map.get(from).offer(to);
        }
        return map;
    }

    public void dfs(Map<String, PriorityQueue<String>> map, String start){
        if(map.containsKey(start)){
            PriorityQueue<String> nextCityPQ = map.get(start); 
            while(nextCityPQ.size() > 0){
                String nextCity = nextCityPQ.poll();
                dfs(map, nextCity);
            }
        }
        
        res.add(start);
    }
}