I have used two method to solve this problem, the first one is a DFS using stack, the second one is backtrace. The backtrace one only uses 14ms, and the one with stack used 25ms. Personally, I prefer to use backtrace methods, because it is easy to understand, and it kind of has a "template" which you can apply to almost all backtrace problems.

This is a DFS using stack:

```
public class Solution {
public List<String> findItinerary(String[][] tickets) {
List<String> result = new ArrayList();
if(tickets == null || tickets.length == 0){
return result;
}
Map<String, ArrayList<String>> graph = new HashMap();
for(int i=0; i<tickets.length; i++){
if(!graph.containsKey(tickets[i][0])){
ArrayList<String> adj = new ArrayList();
adj.add(tickets[i][1]);
graph.put(tickets[i][0], adj);
}else{
ArrayList<String> newadj = graph.get(tickets[i][0]);
newadj.add(tickets[i][1]);
graph.put(tickets[i][0], newadj);
}
}
for(ArrayList<String> a : graph.values()){
Collections.sort(a);
}
Stack<String> stack = new Stack();
stack.push("JFK");
while(!stack.isEmpty()){
while(graph.containsKey(stack.peek()) && !graph.get(stack.peek()).isEmpty()){
stack.push(graph.get(stack.peek()).remove(0));
}
result.add(0,stack.pop());
}
return result;
}
}
```

This one is a backtrace method with recursion:

```
public class Solution {
public List<String> findItinerary(String[][] tickets) {
List<String> result = new ArrayList();
if(tickets == null || tickets.length == 0){
return result;
}
Map<String, ArrayList<String>> graph = new HashMap();
for(int i=0; i<tickets.length; i++){
if(!graph.containsKey(tickets[i][0])){
ArrayList<String> adj = new ArrayList();
adj.add(tickets[i][1]);
graph.put(tickets[i][0], adj);
}else{
ArrayList<String> newadj = graph.get(tickets[i][0]);
newadj.add(tickets[i][1]);
graph.put(tickets[i][0], newadj);
}
}
for(ArrayList<String> a : graph.values()){
Collections.sort(a);
}
backtracing(result, "JFK", graph);
return result;
}
public void backtracing(List<String> result, String current, Map<String, ArrayList<String>> graph){
while(graph.containsKey(current) && !graph.get(current).isEmpty()){
String s = graph.get(current).remove(0);
backtracing(result, s, graph);
}
result.add(0,current);
}
}
```