题目描述

python中没有自动排序的数据结构，所以利用heap来代替

代码

import heapq
class Solution(object):
    def findItinerary(self, tickets):
        """
        :type tickets: List[List[str]]
        :rtype: List[str]
        """
        self.res = []
        self.fromTo = collections.defaultdict(list)

        # 使用堆来储存to数组，保证能pop出字典序最小的
        for from_,to_ in tickets:
            heapq.heappush(self.fromTo[from_], to_)

        self.helper("JFK")

        return self.res[::-1]


    def helper(self, from_):
        # 欧拉路径，终点的入度要比出度大一
        # 所以当我们遍历到一个节点，发现它有from，但是没有to，那说明这个点是终点，于是我们把这个点个加到res
        # 然后退递归，把前面的路程的每个点都加到res里
        # 结果来到起点，起点是最后一个被加进去的
        while self.fromTo[from_]:
            next = heapq.heappop(self.fromTo[from_])
            self.helper(next)
        self.res.append(from_)