Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

One submission to pass. Yaay!

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List<List<Integer>> pathSum(TreeNode root, int sum) { List<List<Integer>> result = new LinkedList<List<Integer>>(); List<Integer> path = new LinkedList<Integer>(); dfs(root,result,path,0,sum); return result; } void dfs(TreeNode root,List<List<Integer>> result, List<Integer> path,int curSum,int sum){ if(root==null)return; curSum+=root.val; path.add(root.val); //at leaf node, decide if new list should be created according to sum matching if(root.left==null&&root.right==null&&curSum==sum){ LinkedList<Integer> aList= new LinkedList<Integer>(); aList.addAll(path); result.add(aList); path.clear(); return; } //left List<Integer> newList = new LinkedList<Integer>(); newList.addAll(path);//use a different list to reserve same path for right dfs(root.left,result,newList,curSum,sum); newList.clear(); newList.addAll(path); dfs(root.right,result,newList,curSum,sum); } }

Reconstruct Itinerary

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:

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 may 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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

package array; import java.util.HashMap; import java.util.LinkedList; import java.util.List; import java.util.Map; import java.util.PriorityQueue; public class ResonstructIternenary { public List<String> findItinerary(String[][] tickets) { // construct adjacency list, make its adjacency list sorted // make sure it is really a list and not set. use set when it does not allow // duplication //sorted list in java can be priority queue Map<String, PriorityQueue<String>> adl = new HashMap<String, PriorityQueue<String>>(); for (String[] ft : tickets) { PriorityQueue<String> to = adl.get(ft[0]); if (to == null) to = new PriorityQueue<String>();// so every from node has a // queue even it is empty to.add(ft[1]); adl.put(ft[0], to); } //to hold the path LinkedList<String> itinerary = new LinkedList<String>(); dfs(adl, "JFK", itinerary); return itinerary; } /** * depth first traversal following the minimum ordered destinations * remove the destination from adjacency list so that it won't be visited twice * when no further destination to go further, put the destination to the path * * @param adl * @param string * @param itinerary */ private void dfs(Map<String, PriorityQueue<String>> adl, String from, LinkedList<String> itinerary) { while (adl.keySet().contains(from) && adl.get(from).size() > 0) { dfs(adl, adl.get(from).poll(), itinerary); } // it will reach to here after dfs is done, which means reaching to // deepest leaves from current node // the stack of nested calls keeps the order of node visiting. reflect // it by adding to from of list itinerary.addFirst(from); } public static void main(String[] args) { ResonstructIternenary o = new ResonstructIternenary(); String[][] tickets = { { "JFK", "SFO" }, { "JFK", "ATL" }, { "SFO", "JFK" } }; List<String> itinerary = o.findItinerary(tickets); System.out.println(itinerary); } }