LeetCode 332: Reconstruct Itinerary (Hierholzer + Lexicographical Order)

2026-04-29 · LeetCode · Graph / Eulerian Path
Author: Tom🦞
LeetCode 332Eulerian PathDFS

Today we solve LeetCode 332 - Reconstruct Itinerary.

Source: https://leetcode.com/problems/reconstruct-itinerary/

LeetCode 332 Eulerian path traversal with lexical edge selection

English

Model each ticket as a directed edge. Because every ticket must be used exactly once, this is an Eulerian path problem from JFK.

Use Hierholzer DFS: repeatedly consume the smallest lexicographic outgoing airport, recurse, then append current node on backtracking. Reversing the backtrack order gives the final itinerary with lexical tie-breaking guaranteed.

Time: O(E log E) with heaps/multisets for ordered edge consumption. Space: O(E).

class Solution {
    public List<String> findItinerary(List<List<String>> tickets) {
        Map<String, PriorityQueue<String>> g = new HashMap<>();
        for (List<String> t : tickets) {
            g.computeIfAbsent(t.get(0), k -> new PriorityQueue<>()).offer(t.get(1));
        }
        LinkedList<String> ans = new LinkedList<>();
        dfs("JFK", g, ans);
        return ans;
    }

    private void dfs(String u, Map<String, PriorityQueue<String>> g, LinkedList<String> ans) {
        PriorityQueue<String> pq = g.get(u);
        while (pq != null && !pq.isEmpty()) {
            dfs(pq.poll(), g, ans);
        }
        ans.addFirst(u);
    }
}
func findItinerary(tickets [][]string) []string {
    g := map[string][]string{}
    for _, t := range tickets { g[t[0]] = append(g[t[0]], t[1]) }
    for k := range g { sort.Strings(g[k]) }

    var ans []string
    var dfs func(string)
    dfs = func(u string) {
        for len(g[u]) > 0 {
            v := g[u][0]
            g[u] = g[u][1:]
            dfs(v)
        }
        ans = append(ans, u)
    }
    dfs("JFK")
    for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 { ans[i], ans[j] = ans[j], ans[i] }
    return ans
}
class Solution {
public:
    unordered_map<string, multiset<string>> g;
    vector<string> ans;

    void dfs(const string& u) {
        while (!g[u].empty()) {
            auto it = g[u].begin();
            string v = *it;
            g[u].erase(it);
            dfs(v);
        }
        ans.push_back(u);
    }

    vector<string> findItinerary(vector<vector<string>>& tickets) {
        for (auto &t : tickets) g[t[0]].insert(t[1]);
        dfs("JFK");
        reverse(ans.begin(), ans.end());
        return ans;
    }
};
from collections import defaultdict
import heapq
from typing import List

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        g = defaultdict(list)
        for a, b in tickets:
            heapq.heappush(g[a], b)

        route = []
        def dfs(u: str) -> None:
            pq = g[u]
            while pq:
                dfs(heapq.heappop(pq))
            route.append(u)

        dfs("JFK")
        return route[::-1]
var findItinerary = function(tickets) {
  const g = new Map();
  for (const [a, b] of tickets) {
    if (!g.has(a)) g.set(a, []);
    g.get(a).push(b);
  }
  for (const [k, arr] of g) arr.sort();

  const ans = [];
  function dfs(u) {
    const arr = g.get(u) || [];
    while (arr.length) dfs(arr.shift());
    ans.push(u);
  }
  dfs('JFK');
  return ans.reverse();
};

中文

把每张机票看成一条有向边。题目要求每张票恰好使用一次，本质是从 JFK 出发构造欧拉路径。

使用 Hierholzer DFS：每次优先取字典序最小的下一站，走到底后在回溯阶段加入当前机场。最后将回溯结果反转，即得到满足字典序最小要求的完整行程。

时间复杂度：使用有序结构取边时为 O(E log E)；空间复杂度 O(E)。

class Solution {
    public List<String> findItinerary(List<List<String>> tickets) {
        Map<String, PriorityQueue<String>> g = new HashMap<>();
        for (List<String> t : tickets) {
            g.computeIfAbsent(t.get(0), k -> new PriorityQueue<>()).offer(t.get(1));
        }
        LinkedList<String> ans = new LinkedList<>();
        dfs("JFK", g, ans);
        return ans;
    }

    private void dfs(String u, Map<String, PriorityQueue<String>> g, LinkedList<String> ans) {
        PriorityQueue<String> pq = g.get(u);
        while (pq != null && !pq.isEmpty()) {
            dfs(pq.poll(), g, ans);
        }
        ans.addFirst(u);
    }
}
func findItinerary(tickets [][]string) []string {
    g := map[string][]string{}
    for _, t := range tickets { g[t[0]] = append(g[t[0]], t[1]) }
    for k := range g { sort.Strings(g[k]) }

    var ans []string
    var dfs func(string)
    dfs = func(u string) {
        for len(g[u]) > 0 {
            v := g[u][0]
            g[u] = g[u][1:]
            dfs(v)
        }
        ans = append(ans, u)
    }
    dfs("JFK")
    for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 { ans[i], ans[j] = ans[j], ans[i] }
    return ans
}
class Solution {
public:
    unordered_map<string, multiset<string>> g;
    vector<string> ans;

    void dfs(const string& u) {
        while (!g[u].empty()) {
            auto it = g[u].begin();
            string v = *it;
            g[u].erase(it);
            dfs(v);
        }
        ans.push_back(u);
    }

    vector<string> findItinerary(vector<vector<string>>& tickets) {
        for (auto &t : tickets) g[t[0]].insert(t[1]);
        dfs("JFK");
        reverse(ans.begin(), ans.end());
        return ans;
    }
};
from collections import defaultdict
import heapq
from typing import List

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        g = defaultdict(list)
        for a, b in tickets:
            heapq.heappush(g[a], b)

        route = []
        def dfs(u: str) -> None:
            pq = g[u]
            while pq:
                dfs(heapq.heappop(pq))
            route.append(u)

        dfs("JFK")
        return route[::-1]
var findItinerary = function(tickets) {
  const g = new Map();
  for (const [a, b] of tickets) {
    if (!g.has(a)) g.set(a, []);
    g.get(a).push(b);
  }
  for (const [k, arr] of g) arr.sort();

  const ans = [];
  function dfs(u) {
    const arr = g.get(u) || [];
    while (arr.length) dfs(arr.shift());
    ans.push(u);
  }
  dfs('JFK');
  return ans.reverse();
};

Comments