332. 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"].

Example 2:
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.

var findItinerary = function(tickets) {
    var m = {};
    var res = [];
    var num = tickets.length;
    if (num <= 0) {
        return res;
    }
    //遍历数组，把每个起点对应的所有终点存在一个数组里，并以起点为键存在一个map里
    for (let i = 0;i < num;i++) {
        if (m[tickets[i][0]]===undefined)
            m[tickets[i][0]] = [tickets[i][1]];
        else 
            m[tickets[i][0]].push(tickets[i][1]);
    }
    //s用来回溯，当节点不是终点时，就继续往下找，是终点时就pop出来存在结果里
    var s = [];
    s.push("JFK");
    while (s.length!==0) {
        var next = s[s.length - 1];
        //如果栈顶元素找不到下一跳，就说明当前栈顶元素已经是终点了
        //这个结论建立在题目中说一定有用到所有机票的解的前提上
        if (m[next]===undefined) {
            res.unshift(next);
            s.pop();
        //栈顶元素还有下一跳，说明可以继续走下去
        } else {
            var temp = m[next][0];
            var tempIndex = 0;
            //找到其下一跳中字母序最小的那个
            for (let i = 0;i<m[next].length;i++) {
                if (temp>m[next][i]) {
                    temp=m[next][i];
                    tempIndex = i;
                }
            }
            //压到栈里，并删除这条记录，代表这条路已经走过了
            s.push(m[next][tempIndex]);
            m[next].splice(tempIndex,1);
            if (m[next].length ===0) 
                m[next] = undefined;
        }
    }
    return res;
};