173. Binary Search Tree Iterator

It is the same algorithm as we do the inorder traversal. Use O(h) memory with stack. The hasNext has worst O(1) run time while next() has worst O(h) time and average O(1) run time.

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

166. Fraction to Recurring Decimal

166. Fraction to Recurring Decimal
There are too many corner cases for this problem when numerator and denominator are Integer.MIN_VALUE, so convert them to long type to avoid taking care of corner cases.
Basically, it will keep calculating reminder until either it equals to 0 or it appears before(repeating decimal). Use hashmap to store the position of the reminder, so when it reappears, we can insert '(' to the right position.

  public String fractionToDecimal(int numerator, int denominator) {  

     boolean neg=(numerator>0 && denominator<0) || (numerator<0 && denominator>0);  
     long numLong=Math.abs((long)numerator);  
     long denomLong=Math.abs((long)denominator);  
     long res=numLong/denomLong;  
     numLong=numLong%denomLong;  
     StringBuilder sb=new StringBuilder();  
     if(neg) sb.append("-");  
     sb.append(Math.abs(res));  
     if(numLong==0) return sb.toString();  
     sb.append('.');  
     HashMap<Long,Integer> used=new HashMap<Long,Integer>();  
     while(numLong!=0 && !used.containsKey(numLong)){  
       used.put(numLong,sb.length());  
       sb.append(numLong*10/denomLong);  
       numLong=numLong*10%denomLong;  
     }  
     if(numLong!=0)  
     {  
      sb.append(")");  
      sb.insert(used.get(numLong),"(");  
     }  
     return sb.toString();  
   }  

162. Find Peak Element (More concise solution)

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

124. Binary Tree Maximum Path Sum

 public int maxPathSum(TreeNode root) {  
     int[] max=new int[1];  
     max[0]=Integer.MIN_VALUE;  
     helper(max,root);  
     return max[0];  
   }  
   public int helper(int[] max,TreeNode root){  
     if(root==null) return 0;  
     int leftMax=helper(max,root.left);  
     int rightMax=helper(max,root.right);  
     int localMax=Math.max(root.val,root.val+Math.max(leftMax,rightMax));  
     max[0]=Math.max(max[0],Math.max(localMax,root.val+leftMax+rightMax));  
     return localMax;  
   }