|
| 1 | +packagemedium; |
| 2 | + |
| 3 | +importclasses.TreeNode; |
| 4 | + |
| 5 | +importjava.util.ArrayList; |
| 6 | +importjava.util.HashMap; |
| 7 | +importjava.util.LinkedList; |
| 8 | +importjava.util.List; |
| 9 | +importjava.util.Map; |
| 10 | +importjava.util.Queue; |
| 11 | +importjava.util.TreeMap; |
| 12 | + |
| 13 | +publicclassBinaryTreeVerticalOrderTraversal { |
| 14 | +publicList<List<Integer>>verticalOrder_using_treemap(TreeNoderoot) { |
| 15 | +List<List<Integer>>result =newArrayList(); |
| 16 | +if(root ==null)returnresult; |
| 17 | +Queue<TreeNode>bfsQ =newLinkedList(); |
| 18 | +Queue<Integer>indexQ =newLinkedList(); |
| 19 | +TreeMap<Integer,List<Integer>>map =newTreeMap(); |
| 20 | +bfsQ.offer(root); |
| 21 | +indexQ.offer(0);//we set the root as index 0, left will be negative, right will be positive |
| 22 | +while(!bfsQ.isEmpty()){ |
| 23 | +intqSize =bfsQ.size(); |
| 24 | +for(inti =0;i <qSize;i++){ |
| 25 | +TreeNodecurr =bfsQ.poll(); |
| 26 | +intindex =indexQ.poll(); |
| 27 | +if(map.containsKey(index)){ |
| 28 | +map.get(index).add(curr.val); |
| 29 | + }elseif(!map.containsKey(index)){ |
| 30 | +List<Integer>list =newArrayList(); |
| 31 | +list.add(curr.val); |
| 32 | +map.put(index,list); |
| 33 | + } |
| 34 | +if(curr.left !=null){ |
| 35 | +bfsQ.offer(curr.left); |
| 36 | +indexQ.offer(index-1); |
| 37 | + } |
| 38 | +if(curr.right !=null){ |
| 39 | +bfsQ.offer(curr.right); |
| 40 | +indexQ.offer(index+1); |
| 41 | + } |
| 42 | + } |
| 43 | + } |
| 44 | +for(inti :map.keySet()){ |
| 45 | +result.add(map.get(i)); |
| 46 | + } |
| 47 | +returnresult; |
| 48 | + } |
| 49 | + |
| 50 | +publicList<List<Integer>>verticalOrder_using_hashmap(TreeNoderoot) { |
| 51 | +List<List<Integer>>result =newArrayList(); |
| 52 | +if(root ==null)returnresult; |
| 53 | +Queue<TreeNode>bfsQ =newLinkedList(); |
| 54 | +Queue<Integer>indexQ =newLinkedList(); |
| 55 | +HashMap<Integer,List<Integer>>map =newHashMap(); |
| 56 | +bfsQ.offer(root); |
| 57 | +indexQ.offer(0);//we set the root as index 0, left will be negative, right will be positive |
| 58 | +intmin =0,max =0; |
| 59 | +while(!bfsQ.isEmpty()){ |
| 60 | +intqSize =bfsQ.size(); |
| 61 | +for(inti =0;i <qSize;i++){ |
| 62 | +TreeNodecurr =bfsQ.poll(); |
| 63 | +intindex =indexQ.poll(); |
| 64 | +if(map.containsKey(index)){ |
| 65 | +map.get(index).add(curr.val); |
| 66 | + }elseif(!map.containsKey(index)){ |
| 67 | +List<Integer>list =newArrayList(); |
| 68 | +list.add(curr.val); |
| 69 | +map.put(index,list); |
| 70 | + } |
| 71 | +if(curr.left !=null){ |
| 72 | +bfsQ.offer(curr.left); |
| 73 | +indexQ.offer(index-1); |
| 74 | +min =Math.min(min,index-1); |
| 75 | + } |
| 76 | +if(curr.right !=null){ |
| 77 | +bfsQ.offer(curr.right); |
| 78 | +indexQ.offer(index+1); |
| 79 | +max =Math.max(max,index+1); |
| 80 | + } |
| 81 | + } |
| 82 | + } |
| 83 | +for(inti =min;i <=max;i++){ |
| 84 | +result.add(map.get(i)); |
| 85 | + } |
| 86 | +returnresult; |
| 87 | + } |
| 88 | + |
| 89 | +} |