[LeetCode] Reconstruct Itinerary

题目

Given a list of airline tickets rePResented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK. Note: If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary [“JFK”, “LGA”] has a smaller lexical order than [“JFK”, “LGB”]. All airports are represented by three capital letters (IATA code). You may assume all tickets form at least one valid itinerary. Example 1: tickets = [[“MUC”, “LHR”], [“JFK”, “MUC”], [“SFO”, “SJC”], [“LHR”, “SFO”]] Return [“JFK”, “MUC”, “LHR”, “SFO”, “SJC”].

解题

题目大意是找一条路径，可以从头到尾的罗列出每个航站。其实就是一个有向图，然后一笔画画完所有的点，按顺序列出所有的点。也就是欧拉路径的定义。 首先题目定义，必然存在一条欧拉路径，且每个点有多个路径按字典序排序。首先采用dfs寻找字典序最小的一条路径，直到某点阻塞，不能通往新的点，那么这一点必然是欧拉路径的终点。也就得到了一条从起点到终点的路径L。 对于路径中的其它点，只能和路径组成环，在dfs递归回退的过程中，每一点继续dfs遍历，最终会阻塞在L上，并组成一个环，回退该路径并记录即可。相当于在每个点寻找到L的路径，并将其并回L。同时递推回归的过程中，先回归的点在路径的后面，所以要逆着记录进链表。