Reconstruct Itinerary，是Google、yelp等公司的高頻面試題。
本期習題講解，我們就通過這道題目，介紹如何將具體的問題抽象成為一個圖遍歷問題求解。
先一起來看看題目：
題目描述
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.
Input/Output:
List
Example:
tickets = ["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Return ["JFK","ATL","JFK","SFO","ATL","SFO"].
Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical order.
考點解析
Reconstruct Itinerary是一道Google, Yelp等公司常考的面經題。乍一看不好解決，但稍微分析一下不難發現，
這道題目的本質就是考察有向圖的遍歷。我們需要不斷的練習和提高自己的抽象能力，將實際問題轉化成常見的算法問題來解決。作為一個工程師，我們平時真正要解決的都是這類實際問題，而現在各大公司面試中也會著重考察透過現象看本質的能力。
今天的習題講解，我們就通過這道題目講解一下如何對一個有向圖進行邊遍歷。並且，講解歐拉路徑，及求解歐拉路徑的相關算法。
主講人：Jack Sun老師
FLGU一線公司資深工程師
進入來Offer官網觀看: www.laioffer.com
解題思路
在這道題目中，Jack Sun老師講解了兩個不同的解法，一個是Brute Force的解法，另一個是利用歐拉路徑的概念實現的更加優化的算法。
Brute Force解法
這道題目是一個比較具體的問題，我們可以將它轉化成一個圖來描述。圖中每一個點就是一個地點，每張票代表的就是兩個地點之間的連線，也就是一個有向的邊。
如下面的例子所示：
input [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
這個題目一個最直接的想法就是從起點JFK開始，嘗試所有可能的路徑，並返回第一個用完全部ticket的路徑。
具體來說分為以下幾步完成：
把input由票的形式轉換成為圖的形式，給定一個點，就能快速地知道它所連接的鄰居點們，並且以lexical order的順序的訪問它們。
在這裡一個intuitive的數據結構就是：HashMap
在構造的圖上從JFK開始做DFS，訪問所有能走的路，同時remove掉訪問過的邊，如果走到一個地方走不通了，我們再利用backtrack回去。
那麼對於這個例子來說，我們最終找到的就是：
Eulerian Path 歐拉路徑
這道題目實際上有一個更好的解法，就是歐拉路徑。
歐拉路徑
In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph which visits every edge exactly once.
這個和這個題目的要求，每個票只用一次，並且全部要用到，是完全符合的。
那麼，這個題目就可以轉化成：已知圖中存在歐拉路徑，如何找到一個歐拉路徑？
今天我們著重講解一下求歐拉路徑的一個經典算法：Hierholzer。
我們看一下Hierholzer算法的偽代碼：
那麼將這個算法應用到這道題目中，我們只需要在構造好圖以後，從JFK開始做DFS，最後將path返回就可以了。
這道題目與經典的hierholzer算法唯一不同的地方是，我們要優先訪問 lexical order比較小的點。
代碼實現
算法與代碼中需要注意的細節處理及時間、空間複雜度分析請觀看視頻講解。
E/N/D
閱讀更多 LaiOffer來Offer 的文章
