187. Repeated DNA Sequences Leetcode

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

For example,

Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",

Return:
["AAAAACCCCC", "CCCCCAAAAA"].

Solution:

Rolling hash and hashtable. 

Since there are only 4 possible letters, we can build a rolling hash with base of 5 and calculate hashcode for each 10-letter-long subsequences.

If we define code('A'):1, code('C'):2; code('G'):3; code('T'):4, Then the hashcode for the first 10-letter-long sequence will be 1*5^0+1*5^1+1*5^2+...2*5^5+...2*5^9. The advantage of rolling hash method is that we don't need to recalculate the hash code from the beginning of the next 10-letter-long sequence, we can calculate the hash code hc[i] based on last hash code hc[i-1]. hc[i]=hc[i-1]/5+code(s.charAt(i))*5^9. It is guranteed that unique DNA sequence will have unique hashcode. By using a hashtable, we can see whether the sequence is occurred more than once.

 public List<String> findRepeatedDnaSequences(String s) {  
     List<String> res=new ArrayList<String>();  
     if(s==null || s.length()<10) return res;  
     HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();  
     int hashCode=0;  
     int base=1;  
     for(int i=0;i<10;i++){  
       hashCode+=getCode(s.charAt(i))*base;  
       base*=5;  
     }  
    map.put(hashCode,1);  
    base=base/5;  
    for(int i=10;i<s.length();i++){  
      hashCode=hashCode/5+getCode(s.charAt(i))*base;  
      if(!map.containsKey(hashCode)) map.put(hashCode,1);  
      else{  
        if(map.get(hashCode)==1) {  
          res.add(s.substring(i-9,i+1));  
          map.put(hashCode,2);  
        }  
      }  
    }  
    return res;  
   }  
   public int getCode(char c){  
     switch (c){  
     case 'A': return 1;  
     case 'C': return 2;  
     case 'G': return 3;  
     case 'T': return 4;  
     default: return 0;  
     }  
   }  

179. Largest Number Leetcode Java

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

Solution:

We need to build a new comparator with a comparison mechanism to sort the array to 9,5,34,3,30. The mechanism is to realize the largest number so if we have two numbers, for example, 30 and 34, there are two ways to form a number, 3034 and 3430, clearly 34 30 will be larger, similarly, using this mechanism, we can sort the array, 30<<3<<34<<5<<9, after we sort the array this way, we can easily find the largest number.

 public String largestNumber(int[] num) {  
     if(num==null || num.length==0) return "";  
     String[] temp=new String[num.length];  
     for(int i=0;i<num.length;i++){  
       temp[i]=String.valueOf(num[i]);  
     }  
     Comparator<String> myComparator=new Comparator<String>(){  
      @Override  
      public int compare(String a, String b){  
        String sa=a+b;  
        String sb=b+a;  
      return sb.compareTo(sa);  
      }  
     };  
     Arrays.sort(temp,myComparator);  
     if(temp[0].equals("0")) return "0";  
     StringBuilder sb=new StringBuilder();  
     for(int i=0;i<temp.length;i++){  
      sb.append(temp[i]);   
     }  
     return sb.toString();  
   }  

173. Binary Search Tree Iterator Leetcode Java

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

Solution:

It is essentially an in order traversal. See 94. Binary tree in order traversal

Here I use a stack to realize the in order traversal. 

 public class BSTIterator {  
    Stack<TreeNode> st;  
   public BSTIterator(TreeNode root) {  
     st=new Stack<TreeNode>();  
     while(root!=null){  
       st.push(root);  
       root=root.left;  
     }  
   }  
   /** @return whether we have a next smallest number */  
   public boolean hasNext() {  
    return !st.isEmpty();   
   }  
   /** @return the next smallest number */  
   public int next() {  
     TreeNode cur=st.pop();  
     int samll=cur.val;  
     cur=cur.right;  
     while(cur!=null){  
       st.push(cur);  
       cur=cur.left;  
     }  
     return samll;  
   }  
 }  

171. Excel Sheet Column Number Leetcode Java

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

    A -> 1
    B -> 2
    C -> 3
    ...
    Z -> 26
    AA -> 27
    AB -> 28 

Solution:

Related to 168. Excel Sheet Column Title

Reversion process of 168. Transform a 26 based number to decimal number.

   public int titleToNumber(String s) {  
    if(s==null || s.length()==0) return 0;  
    int res=0;  
    int div=1;  
    for(int i=s.length()-1;i>=0;i--){  
      res+=div*(s.charAt(i)-'A'+1);  
      div*=26;  
    }  
    return res;  
   }  

168. Excel Sheet Column Title Leetcode Java

Given a positive integer, return its corresponding column title as appear in an Excel sheet.

For example:

    1 -> A
    2 -> B
    3 -> C
    ...
    26 -> Z
    27 -> AA
    28 -> AB 

Solution:

Related to 171. Excel Sheet Column Number

It is a very simple problem, It is just to transform a decimal number to a 26 based number.Just like how we did for transferring from decimal to binary or hexadecimal number. 

 public String convertToTitle(int n) {  
   if(n<=0) return "";  
   StringBuilder sb=new StringBuilder();  
   while(n>0){  
     sb.append((char)('A'+(n-1)%26));  
     n=(n-1)/26;  
   }  
   return sb.reverse().toString();  
   }  

164. Maximum Gap Leetcode Java

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

Solution:

Non-linear time solution. Sort the array and check the gap one by one. O(nlogn).

Linear time solution: Bucket sort.

Assume there are n elements in this array, and the maximum gap must be greater than (max-min)/n-1. Otherwise min+sum(gap[i])<=min+(n-1)*maxGap<max, which is a contradiction.

Therefore, we can divide all elements into (n-1) buckets, and the length of the bucket will be (max-min)/n-1. Since maxGap> (max-min)/n-1, so the two elements that generate the biggest gap must come from two different buckets. For each element in the array, we can easily determine which bucket it located and thus we can maintain a minimumValue and maximumValue for each bucket. By checking bucket[i+1].minValue-bucket[i].maximumValue, we can find the maximum gap.

 public int maximumGap(int[] num) {  
    if(num==null || num.length<2) return 0;  
    int min=Integer.MAX_VALUE;  
    int max=0;  
    for(int i=0;i<num.length;i++){  
      min=Math.min(min,num[i]);  
      max=Math.max(max,num[i]);  
    }  
    int res=(max-min-1)/(num.length-1)+1;  
    int gap=res;  
    int[] minBucket=new int[num.length];  
    for(int i=0;i<num.length;i++) minBucket[i]=max;  
    int[] maxBucket=new int[num.length];  
    for(int i=0;i<num.length;i++){  
      int ind=(num[i]-min)/gap;  
      minBucket[ind]=Math.min(minBucket[ind],num[i]);  
      maxBucket[ind]=Math.max(maxBucket[ind],num[i]);  
    }  
    int pre=0;  
    for(int i=1;i<num.length;i++){  
      if(maxBucket[i]!=0){  
      res=Math.max(res,minBucket[i]-maxBucket[pre]);  
      pre=i;  
      }  
    }  
    return res;  
   }  

162. Find Peak Element Leetcode Java

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

click to show spoilers.

Note:

Your solution should be in logarithmic complexity.

Solution:

The difficulty is to find the peak element in O(logn).

Since num[i]!=num[i+1], for a given middle element, num[m], there will be 4 cases:

1. num[m-1]<num[m]>num[m+1]: num[m] will be the peak element.

2. num[m-1]<num[m]<num[m+1]: there must exist a peak element in the right half. Let's think at that way, in order to make num[m+1] is not the peak element, the following must be true: num[m+1]<num[m+2]; similarly num[m+2] must < num[m+3]...so in order to make num[end-1] is not the peak element, num[end-1]< num[end], thus num[end] is the peak element, because we consider num[n]=-∞. there must exist a peak element in the right half and we can cut the left half.

3. num[m-1]>num[m]>num[m+1], similarly there must exist a peak element in the left half.

4. num[m-1]>num[m]<num[m+1], either half is OK.

When there is only 2 elements in the array, return the bigger one.

 public int findPeakElement(int[] num) {  
     if(num==null || num.length==0) return -1;  
     int l=0;  
     int r=num.length-1;  
     while(l+1<r){  
       int m=(r-l)/2+l;  
       if(num[m]>num[m+1] && num[m]>num[m-1]) return m;  
       else if(num[m]<num[m+1]) l=m+1;  
       else r=m-1;  
     }  
     return (num[l]<=num[r])? r : l;  
   }  

160. Intersection of Two Linked Lists Leetcode Java

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.

Solution:
The easiest way is to count the length of List A and B respectively. And we can get the difference of this two lists, Eg. A has length 5, and B has length 6, so we get the difference of 1 and we set the starting position of pointer i at a1 and j at b2, and traversal the two lists till two pointers met at the intersection points.

My solution is similar, I maintained two pointers curA and curB, starting from a1 and b1 respectively, when curA hit the tail of the A, we set curA = B's head, and when curB hit the tail of B we set curB= A's head, by doing this way, when curB=a1, curA=b2, so when they meet, they will meet at the intersection, or if there is no intersection, they won't meet.

  public ListNode getIntersectionNode(ListNode headA, ListNode headB) {  
    if(headA==null || headB==null) return null;  
    ListNode curA=headA;  
    ListNode curB=headB;  
    int count=0;  
    while(count<2 && curA!=curB){  
      curA=curA.next;  
      curB=curB.next;  
      if(curA==null){  
        curA=headB;  
        count++;  
      }  
      if(curB==null) curB=headA;  
    }  
    if(curA==curB) return curA;  
    return null;  
   }  

155. Min Stack Leetcode Java

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• getMin() -- Retrieve the minimum element in the stack.

Solution:

An easy solution is maintain two stacks and one of them s1 is to store the normal elements the other one s2 stores the minimum elements so for. So whenever there is push, s1.push(x), s2.push(Math.Min(x,min)). For pop(), both two stacks will pop, and getMin() will be s2.peek().

An advanced solution is just push min to s2 when the min is changed which means the current x become the new min. When doing the pop(), we do the same thing, check if the popped element from s1 is the top element in s2, if yes, pop s2 as well. Eg. now we push the following elements: 3,4,2,5 in s2, we only needs to push 3,2. Because even when we pop 5 out of s1, it won't affect the minimum which is 2. But when we pop out 2 from s1, we have to pop out 2 from s2 as well, that because the minimum has been popped out, and the minimum becomes the 3, which is minimum of current s1(3,4).  This solution will save little spaces for the average case, but for worst case, they use same space.

     class MinStack {  
   Stack<Integer> st=new Stack<Integer>();  
   Stack<Integer> min=new Stack<Integer>();  
   public void push(int x) {  
     st.push(x);  
     if(min.isEmpty() || x<=min.peek()) min.push(x);  
   }  
   public void pop() {  
     int x=st.pop();  
     if(!min.isEmpty() && min.peek()==x) min.pop();  
   }  
   public int top() {  
     return st.peek();  
   }  
   public int getMin() {  
     return min.peek();  
   }  
 }  

154. Find Minimum in Rotated Sorted Array II Leetcode Java

Follow up for "Find Minimum in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

The array may contain duplicates.

Solution:

All related problems:

33. Search in Rotated Sorted Array

81. Search in Rotated Sorted Array II 

153. Find Minimum in Rotated Sorted Array

154. Find Minimum in Rotated Sorted Array II

The duplicate number will cause that we can't determine which half is sorted when A[m]==A[r].

So for A[m]==A[r], we can't cut the array half, the only element we can exclude is A[r]. because even it is the minimum, we still have A[m](also the minimum) in the remaining array.

Duplication will degrade the time complexity to O(n)

      public int findMin(int[] num) {  
     if(num==null || num.length==0) return 0;  
     int l=0;  
     int r=num.length-1;  
     while(l<r){  
       int m=(r-l)/2+l;  
       if(num[m]<num[r]) r=m;  
       else if(num[m]>num[r]) l=m+1;  
       else r--;  
     }  
     return num[l];  
   }  

153. Find Minimum in Rotated Sorted Array Leetcode Java

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

Solution:

All related problems:
33. Search in Rotated Sorted Array
81. Search in Rotated Sorted Array II 
153. Find Minimum in Rotated Sorted Array
154. Find Minimum in Rotated Sorted Array II
It is very similar to previous rotated sorted array problem. If there is no duplicated element in the array, according to the relationship between A[mid] and A[r], we can determine whether the left half is sorted or the right half is sorted. With this information we can cut the unnecessary half and find the minimum element. 

two cases:

 1.if right half is sorted, the minimum must between l and m(inclusive)

 2. if left half is sorted(right half is not sorted), the minimum must between m+1 and r(inclusive). 

Must compare with right and first determine if right half is sorted to avoid the corner case that the array is complete sorted. So eg. if left half is sorted and right half is sorted as well, we can't say the minimum is in the right half. It is very important that right half is not sorted for the second case.
Time complexity: O(logn)

   public int findMin(int[] num) {  
    if(num==null || num.length==0) return 0;  
    int l=0;  
    int r=num.length-1;  
    while(l<r){  
      int m=(r-l)/2+l;  
      if(num[m]<num[r]){ //right half is sorted  
        r=m;  
      }  
      else l=m+1;  
    }  
    return num[l];  
   }  

152. Maximum Product Subarray Leetcode Java

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

Solution:

It is a similar but more difficult problem of 53. maximum subarray. 

We will use the same technique, local and global technique. Please refer problem 53. maximum subarray for more information.

The difference is that when we do the summation, only positive number will make the final result better, while negative won't, so that, we can reset the sum to 0, rather than use the aggregated negative number. 

But for production, it is also possible that a negative number multiply another negative number to make the product very big.

So we need to maintain not only the biggest product till current element(local max, must use current element), but also the minimum as well. Because the minimum one(possibly the most negative number) multiply the current number(possibly a negative number) will become the maximum product so far. 
The recursion equation is like this: Min[i]=Math.Min(A[i],Max[i-1]* A[i], Min[i-1]*A[i]), similarly Max[i]= Math.max(A[i],Max[i-1]* A[i], Min[i-1]*A[i]);

   public int maxProduct(int[] A) {  
    if(A==null || A.length==0) return 0;  
    int localMin=A[0];  
    int localMax=A[0];  
    int globalMax=A[0];  
    for(int i=1;i<A.length;i++){  
      int temp=localMax;  
      localMax=Math.max(Math.max(A[i],localMax*A[i]),localMin*A[i]);  
      localMin=Math.min(Math.min(A[i],localMin*A[i]),temp*A[i]);  
      globalMax=Math.max(globalMax,localMax);  
    }  
    return globalMax;  
   }  

151. Reverse Words in a String Leetcode Java

Given an input string, reverse the string word by word.

For example,
Given s = "the sky is blue",
return "blue is sky the".

Solution:

The basic idea is to determine the position of the white spaces between each word. Use a pointer named tail to track last position of the white space. Make sure the substring is a valid word by check if there are non-space characters between current white space and the tail white space. 

 public String reverseWords(String s) {  
    s=s.trim();  
    StringBuilder sb=new StringBuilder();  
    int tail=s.length();  
    for(int j=s.length()-1;j>=0;j--){  
      if(j<s.length()-1 && s.charAt(j)==' ' && s.charAt(j+1)!=' '){  
        if(tail!=s.length()) sb.append(' ');  
        sb.append(s.substring(j+1,tail));  
        tail=j;  
      }  
      else if(s.charAt(j)==' ') tail=j;  
      else continue;  
    }  
    if(tail!=s.length()) sb.append(' ');  
    sb.append(s.substring(0,tail));  
    return sb.toString();  
   }  

150. Evaluate Reverse Polish Notation Leetcode Java

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

Solution:

A stack is used in my solution to realize the calculating of the reverse polish notation. Here we suppose the input are all good. 

Each time when we encounter a operators we pop out two integers from the stack to form the expression and calculate the current result and push it back to the stack.

 public ListNode sortList(ListNode head) {  
     return mergeSort(head);  
   }  
   public ListNode mergeSort(ListNode head){  
     if(head==null || head.next==null) return head;  
     ListNode runner=head.next;  
     ListNode walker=head;  
     while(runner!=null && runner.next!=null){  
       walker=walker.next;  
       runner=runner.next.next;  
     }  
     ListNode head2=walker.next;  
     walker.next=null;  
     return MergeTwo(mergeSort(head),mergeSort(head2));  
   }  
   public ListNode MergeTwo(ListNode l1,ListNode l2){  
     ListNode preDummy=new ListNode(0);  
     preDummy.next=l1;  
     ListNode pre=preDummy;  
     while(pre.next!=null && l2!=null){  
       if(pre.next.val>l2.val){  
         ListNode temp=l2.next;  
         l2.next=pre.next;  
         pre.next=l2;  
         l2=temp;  
       }  
       pre=pre.next;  
     }  
     if(pre.next==null) pre.next=l2;  
     return preDummy.next;  
   }  

148. Sort List Leetcode Java

Sort a linked list in O(n log n) time using constant space complexity.
Solution:
Strictly speaking, my solution is not a constant space solution.
I use the idea of merge sort. So the basic steps are:
Divide the current list to half till only one node or no node in the list, then merge them back by using merge two sorted list.
The extra space should be the recursion tree space which is O(logn) and the time complexity will be O(nlogn)

 public ListNode sortList(ListNode head) {  
     return mergeSort(head);  
   }  
   public ListNode mergeSort(ListNode head){  
     if(head==null || head.next==null) return head;  
     ListNode runner=head.next;  
     ListNode walker=head;  
     while(runner!=null && runner.next!=null){  
       walker=walker.next;  
       runner=runner.next.next;  
     }  
     ListNode head2=walker.next;  
     walker.next=null;  
     return MergeTwo(mergeSort(head),mergeSort(head2));  
   }  
   public ListNode MergeTwo(ListNode l1,ListNode l2){  
     ListNode preDummy=new ListNode(0);  
     preDummy.next=l1;  
     ListNode pre=preDummy;  
     while(pre.next!=null && l2!=null){  
       if(pre.next.val>l2.val){  
         ListNode temp=l2.next;  
         l2.next=pre.next;  
         pre.next=l2;  
         l2=temp;  
       }  
       pre=pre.next;  
     }  
     if(pre.next==null) pre.next=l2;  
     return preDummy.next;  
   }  

147. Insertion Sort List Leetcode Java

Sort a linked list using insertion sort.
Solution:
Just like insertion sort in the array. 
1.Find the insertion position,
2. Insert into the right postion
Have to check if the current node is already in the right position. If yes, do nothing. 

 public ListNode insertionSortList(ListNode head) {  
    if(head==null || head.next==null) return head;  
    ListNode preDummy=new ListNode(0);  
    preDummy.next=head;  
    ListNode tail=head;  
    while(tail.next!=null){  
      ListNode cur=tail.next;  
      ListNode pre=preDummy;  
      while(cur.val>pre.next.val) pre=pre.next;  
      if(pre!=tail){  
        tail.next=cur.next;  
        cur.next=pre.next;  
        pre.next=cur;  
      }  
      else tail=tail.next;  
    }  
    return preDummy.next;  
   }  

146. LRU Cache Leetcode Java

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Solution:

Use a doubly linked list and hashmap together to realize the desired functions. A doubly linked list will make the insertion and deletion in O(1). And the get() requires not only retrieving the value but also updating the whole list, since this node is visited. Maintain two extra pointers pre and tail, to get fast insertion and deletion when overflowed. Since it is doubly linked list, we have to take care of the two corner cases: first element and last element. 

 public class LRUCache {  
   class ListNode{  
   int val;  
   ListNode next;  
   ListNode previous;  
   int key;  
   public ListNode(int key, int val) {  
     this.key=key;  
     this.val=val;  
     this.next=null;  
     this.previous=null;  
   }  
 }  
   ListNode pre;  
   ListNode tail;  
   HashMap<Integer,ListNode> map;  
   int capacity;  
   public LRUCache(int capacity) {  
     this.capacity=capacity;  
     this.map=new HashMap<Integer,ListNode>();  
     this.pre=new ListNode(0,0);  
     this.tail=pre;  
   }  
   public int get(int key) {  
     if(map.isEmpty() || !map.containsKey(key)) return -1;  
     ListNode cur=map.get(key);  
     if(cur.previous==pre) return cur.val;  
     if(cur==tail) tail=cur.previous;  
     cur.previous.next=cur.next;  
     if(cur.next!=null) cur.next.previous=cur.previous;  
     cur.next=pre.next;  
     if(pre.next!=null) pre.next.previous=cur;  
     pre.next=cur;  
     cur.previous=pre;  
     return cur.val;  
   }  
   public void set(int key, int value) {  
     if(this.capacity==0) return;  
     if(this.map.isEmpty()){  
       ListNode cur=new ListNode(key,value);  
       pre.next=cur;  
       cur.previous=pre;  
       tail=cur;  
       map.put(key,cur);  
     }  
     else if(this.map.containsKey(key)){  
       ListNode cur=map.get(key);  
       if(cur.previous==pre){  
         cur.val=value;  
         return;  
       }  
       if(cur==tail) tail=cur.previous;  
       cur.previous.next=cur.next;  
       if(cur.next!=null) cur.next.previous=cur.previous;  
       cur.next=pre.next;  
       if(pre.next!=null) pre.next.previous=cur;  
       pre.next=cur;  
       cur.previous=pre;  
       cur.val=value;  
     }  
     else{  
       if(map.size()>=capacity){  
         map.remove(tail.key);  
         tail=tail.previous;  
         tail.next=null;  
       }  
         ListNode cur=new ListNode(key,value);  
         cur.next=pre.next;  
         if(pre.next!=null) pre.next.previous=cur;  
         pre.next=cur;  
         cur.previous=pre;  
         if(map.isEmpty()) tail=cur;  
         map.put(key,cur);  
     }  
   }  
 }  

145. Binary Tree Postorder Traversal Leetcode Java

Given a binary tree, return the postorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

Solution:

Like other 2 traversals, 3 solutions will be presented.
All traversal problems:
94.   Binary Tree Inorder Traversal
144. Binary Tree Preorder Traversal
145. Binary Tree Postorder Traversal

1st, the trivial one: recursive solution

  public List<Integer> postorderTraversal(TreeNode root) {  
    List<Integer> res=new ArrayList<Integer>();  
    helper(root,res);  
    return res;  
   }  
   public void helper(TreeNode root, List<Integer> res){  
     if(root==null) return;  
     helper(root.left,res);  
     helper(root.right,res);  
     res.add(root.val);  
   }  

2nd, Iteration with extra space
It is a little bit more tricky than other two cases, we have to push both left and right to stack. Obviously, if current node's left is not null, we push its left, if cur's right is not null, we have to check if the cur'right has been processed, if so, output cur.

    public List<Integer> postorderTraversal(TreeNode root) {  
    List<Integer> res=new ArrayList<Integer>();  
    if(root==null) return res;  
    Stack<TreeNode> st=new Stack<TreeNode>();  
    TreeNode pre=null;  
    while(root!=null || !st.isEmpty()){  
      if(root!=null){  
        st.push(root);  
        root=root.left;  
      }  
      else{  
        if(st.peek().right==null || st.peek().right==pre){  
          pre=st.pop();  
          res.add(pre.val);  
        }  
        else root=st.peek().right;  
      }  
    }  
    return res;  
   }  

3rd, Iteration with no extra space: Morris transverse using threading.
It is much more complicated than other two cases.
First trick is to create a dummy node and set dummy.left=root, which will avoid taking special case when there root only have right subtree.
Basic steps:
if the cur.left==null, set cur=cur.right
If the cur.left!=null, find the right-most child of cur.left, 
     if cur.left.rightmost.right==null, which means, the current node and cur.left has not been visited, and the rightmost node is the predecessor of cur node, set rightmost.right=cur and cur=cur.left
     if cur.left.rightmost.right=cur, which means the current node has been visited, and cur.left has been processed, so reversely output cur.left.val -> pre.val, restore the tree by set rightmost.right=null, and set cur=cur.right, reverse it back after adding to result list;

Notice that: each edge will be only visited at most twice, so the time complexity still O(2*E)=O(4*V)=O(V). 

 public List<Integer> postorderTraversal(TreeNode root) {  
    List<Integer> res=new ArrayList<Integer>();  
    if(root==null) return res;  
    TreeNode preDummy=new TreeNode(0);  
    preDummy.left=root;  
    TreeNode cur=preDummy;  
    while(cur!=null){  
      if(cur.left==null) cur=cur.right;  
      else{  
        TreeNode pre=cur.left;  
        while(pre.right!=null && pre.right!=cur) pre=pre.right;  
        if(pre.right==null){  
          pre.right=cur;  
          cur=cur.left;  
        }  
        else{  
          pre.right=null;  
          TreeNode head=reverse(cur.left);  
          TreeNode temp=head;  
          while(temp!=null){  
            res.add(temp.val);  
            temp=temp.right;  
          }  
          reverse(head);  
          cur=cur.right;  
        }  
      }  
    }  
    preDummy.left=null;  
    return res;  
   }  
   public TreeNode reverse(TreeNode start){  
     TreeNode head=start;  
     TreeNode pre=start;  
     while(pre.right!=null){  
       TreeNode cur=pre.right;  
       pre.right=cur.right;  
       cur.right=head;  
       head=cur;  
     }  
     return head;  
   }  

144. Binary Tree Preorder Traversal Leetcode Java

Given a binary tree, return the preorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

Solution:

I will present 3 solutions.
All traversal problems:
94.   Binary Tree Inorder Traversal
144. Binary Tree Preorder Traversal
145. Binary Tree Postorder Traversal

1st, the trivial one: recursive solution

 public List<Integer> preorderTraversal(TreeNode root) {  
     List<Integer> res=new ArrayList<Integer>();  
     helper(root,res);  
     return res;  
   }  
   public void helper(TreeNode root, List<Integer> res){  
     if(root==null) return;  
     res.add(root.val);  
     helper(root.left,res);  
     helper(root.right,res);  
   }  

2nd, Iteration with extra space
Use a stack to record the preceding parent node, so when we finish the left node, and we can find its parent node/ preceding node. The difference between this one with inorder tranversal is the timing of adding the root.val to result list. 

 public List<Integer> preorderTraversal(TreeNode root) {  
    List<Integer> res=new ArrayList<Integer>();  
    if(root==null) return res;  
    Stack<TreeNode> st=new Stack<TreeNode>();  
    while(root!=null || !st.isEmpty()){  
      if(root!=null){  
        st.push(root);  
        res.add(root.val);  
        root=root.left;  
      }  
      else{  
        root=st.pop();  
        root=root.right;  
      }  
    }  
    return res;  
   }  

3rd, Iteration with no extra space: Morris Preorder transverse using threading
See these two wiki pages for more information: Morris in order traversal using threading ;
Threaded binary tree. 
Basic idea is to thread the binary tree by creating the links to the in-order predecessor. 
After the thread is created, we can do the preorder traversal and also revert the change to original tree during the traversal.
Basic steps:
if the cur.left==null, add cur.val into result list, set cur=cur.right
If the cur.left!=null, find the right-most child of cur.left, 
     if cur.left.rightmost.right==null, which means, the current node and cur.left has not been visited, and the rightmost node is the predecessor of cur node, set rightmost.right=cur and cur=cur.left
     if cur.left.rightmost.right=cur, which means the current node has been visited, and cur.left has been processed, so output cur.val, restore the tree by set rightmost.right=null, and set cur=cur.right;
The difference between this with inorder traversal is that the timing of adding the root.
For inorder traversal, we add the root.val when we back to root from root.left, but for pre-order traversal, we add root.val when we first visit the root.node and then traversal the root.left, so when we index back to root, we directly jump to root.right.Notice that: each edge will be only visited at most twice, so the time complexity still O(2*E)=O(4*V)=O(V).

 public List<Integer> preorderTraversal(TreeNode root) {  
     List<Integer> res=new ArrayList<Integer>();  
     if(root==null) return res;  
     while(root!=null){  
       if(root.left!=null) {  
         TreeNode pre=root.left;  
         while(pre.right!=null && pre.right!=root){  
           if(pre.right!=null) pre=pre.right;  
           else pre=pre.left;  
         }  
         if(pre.right==root){  
           pre.right=null;  
           root=root.right;  
         }  
         else{  
           pre.right=root;  
           res.add(root.val);  
           root=root.left;  
         }  
       }  
       else{  
         res.add(root.val);  
         root=root.right;  
       }  
     }  
     return res;  
   }