这题做了一天。。一天。。上午拿到之后感觉挺easy的，我想像NQueens那样先DFS找到所有的解。结果怎么也无法跟N-Queens类比上，主要是backtracking的时候很难清空从前的状态。最后投了，参考了的dfs。

public List
    
      findItinerary(String[][] tickets) {		Map
     
      > map = new HashMap<>();		for (String[] ticket : tickets) {			List
      
        dests = map.get(ticket[0]);			if (dests == null) {				dests = new ArrayList<>();				dests.add(ticket[1]);				map.put(ticket[0], dests);			} else {				dests.add(ticket[1]);			}		}		for (List
       
         dests : map.values()) {			Collections.sort(dests);		}		List
        
          res = new ArrayList<>();		res.add("JFK");		dfs(res, map, "JFK", tickets.length);		return res;	}	//	public void dfs(List
         
           res, Map
          
           > map, String src, int length) { if (res.size() == length + 1) { return; } List
           
             dests = map.get(src); if (dests != null && dests.size() > 0) { for (int i = 0; i < dests.size(); i++) { String dest = dests.remove(i); res.add(dest); dfs(res, map, dest, length); if (res.size() == length + 1) return; dests.add(i, dest); res.remove(res.size() - 1); } } }复制代码
           
          
         
        
       
      
     
    

上面的代码挺长的。摘抄一个的 priorityqueue的答案：

public class Solution{	HashMap
    
     > map = new HashMap
     
      >();	LinkedList
      
        result = new LinkedList
       
        (); 	public List
        
          findItinerary(String[][] tickets) {		for (String[] ticket : tickets) {			if (!map.containsKey(ticket[0])) {				PriorityQueue
         
           q = new PriorityQueue
          
           (); map.put(ticket[0], q); } map.get(ticket[0]).offer(ticket[1]); } dfs("JFK"); return result; } public void dfs(String s) { PriorityQueue
           
             q = map.get(s); while (q != null && !q.isEmpty()) { dfs(q.poll()); } result.addFirst(s); }}复制代码
           
          
         
        
       
      
     
    

另外这题还可以用欧拉通路来做： https://leetcode.com/discuss/84659/short-ruby-python-java-c

投了投了。

另外，今天发现一个人的刷题博客(http://www.jianshu.com/u/d709e59ac317)， 被他的第一篇计划燃得一塌糊涂，人的意志力、执行力强起来真让人感动。