本文共 6019 字，大约阅读时间需要 20 分钟。

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:

1. 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"].
2. All airports are represented by three capital letters (IATA code).
3. You may assume all tickets form at least one valid itinerary.

Example 1:

Input: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]Output: ["JFK", "MUC", "LHR", "SFO", "SJC"]

Example 2:

Input: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]Explanation: Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"].             But it is larger in lexical order.

---------------------------------------------------------------------------------------

这题的特殊之处在于，深度优先遍历，参考下图，优先深下去，然后字典序优先的靠前。可以从先序的角度去思考，先序到KUL卡住了，看看另外一棵子树是不是能遍历完，这就是后序的思路了。

从discussion学的别人代码：

class Solution:    def findItineraryNoneRecursive(self, tickets):        d = {}        tickets.sort(key=lambda x: x[1], reverse=True)        for ticket in tickets:            fro, to = ticket[0], ticket[1]            if (fro not in d):                d[fro] = [to]            elif (fro in d):                d[fro].append(to)        revert,sta = [],["JFK"]        while (sta):            while(sta[-1] in d and d[sta[-1]]):                top = d[sta[-1]].pop()                sta.append(top)            revert.append(sta.pop())        return revert[::-1]    def findItinerary(self, tickets):        d = {}        tickets.sort(key=lambda x: x[1], reverse=True)        for ticket in tickets:            fro, to = ticket[0], ticket[1]            if (fro not in d):                d[fro] = [to]            elif (fro in d):                d[fro].append(to)        revert,sta = [],["JFK"]        self.dfs("JFK", d, revert)        return revert[::-1]    def dfs(self, cur, d, revert):        while (cur in d and d[cur]):            self.dfs(d[cur].pop(), d, revert)        revert.append(cur)s = Solution()print(s.findItinerary([["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]])) #['JFK', 'NRT', 'JFK', 'KUL']#print(s.findItinerary([["JFK","KUL"],["JFK","NRT"],["KUL","JFK"]])) #['JFK', 'KUL', 'JFK', 'NRT']#print(s.findItinerary([["JFK","KUL"],["JFK","NRT"],["KUL","JFK"],["NRT","JFK"]])) #['JFK', 'KUL', 'JFK', 'NRT', 'JFK']

后序遍历的思路，这道题学到了一种新玩法post3：

from itertools import permutations# Definition for a binary tree node.class TreeNode:    def __init__(self, x):        self.val = x        self.left = None        self.right = Noneclass Solution:    def p1(self, root):        if (root == None):            return        print(root.val)        self.p1(root.left)        self.p1(root.right)    def p2(self, root):        stack = []        while (root != None or stack):            while (root != None):                print(root.val)                stack.append(root)                root = root.left            if (stack):                root = stack.pop()                root = None if root == None else root.right    def i1(self, root):        if (root == None):            return        self.i1(root.left)        print(root.val)        self.i1(root.right)    def i2(self, root):        stack = []        while (root != None or stack):            while (root != None):                stack.append({'node': root, 'tag': 'l'})                root = root.left            if (stack):                cur = stack.pop()                if (cur["tag"] == 'l'):                    print(cur["node"].val)                    if (cur["node"].right != None):                        stack.append({'node': cur["node"].right, 'tag': 'r'})                    root = None                elif (cur["tag"] == 'r'):                    root = cur["node"]    # i3 is better, inorder doesn't need extra flg in fact    def i3(self, root):        stack = []        while (root != None or stack):            while (root != None):                stack.append(root)                root = root.left            if (stack):                root = stack.pop()                print(root.val)                root = root.right if (root.right != None) else None    def post1(self, root):        if (root == None):            return        self.post1(root.left)        self.post1(root.right)        print(root.val)    def post2(self, root):        stack = []        while (root != None or stack):            while (root != None):                stack.append({'node': root, 'tag': 'l'})                root = root.left            if (stack):                cur = stack.pop()                if (cur["tag"] == 'l'):                    stack.append({'node': cur["node"], 'tag': 'r'})                    root = None if cur["node"].right == None else cur["node"].right                elif (cur["tag"] == 'r'):                    print(cur["node"].val)                    root = None    def get_not_visited_child(self, parent, visited):        if (parent.left and parent.left not in visited):            return parent.left        if (parent.right and parent.right not in visited):            return parent.right        return None    #新玩法    def post3(self,root):        sta = [root]        visited = {root}        revert = []        while (sta):            next = self.get_not_visited_child(sta[-1], visited)            while (next):                sta.append(next)                visited.add(next)                next = self.get_not_visited_child(sta[-1], visited)            if (sta):                revert.append(sta.pop().val)        return revertn1 = TreeNode(1)n2 = TreeNode(2)n3 = TreeNode(3)n4 = TreeNode(4)n5 = TreeNode(5)n6 = TreeNode(6)n7 = TreeNode(7)n1.left = n2n1.right = n3n2.left = n4n2.right = n5n3.left = n6n3.right = n7s = Solution()s.post2(n1)print(s.post3(n1))

更多可以参考

转载地址：http://ktfoi.baihongyu.com/