199. Binary Tree Right Side View

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Solution:
For tree problem, I will provide both iteration and recursion solutions.

Iteration:
Level order, from right to left, add the first element to the result list in each level.
Time complexity O(V)

 public List<Integer> rightSideView(TreeNode root) {  
     List<Integer> res=new ArrayList<Integer>();  
     if(root==null) return res;  
     LinkedList<TreeNode> q =new LinkedList<TreeNode>();  
     q.offer(root);  
     while(!q.isEmpty()){  
       int l=q.size();  
       for(int i=0;i<l;i++){  
         TreeNode temp=q.poll();  
         if(temp.right!=null) q.offer(temp.right);  
         if(temp.left!=null) q.offer(temp.left);  
         if(i==0) res.add(temp.val);  
       }  
     }  
     return res;  
   }  

Recursion
Same idea, transverse the tree from right to left, add the first element in this level to the result list.
Trick: use curLev and result.size() to determine if it is the first element in the current level and make sure only add one element in each level.

 public List<Integer> rightSideView(TreeNode root) {  
     List<Integer> res=new ArrayList<Integer>();  
     helper(root,0,res);  
     return res;  
   }  
   public void helper(TreeNode root, int curLev, List<Integer> res){  
     if(root==null) return;  
     if(curLev==res.size()) res.add(root.val);  
     helper(root.right,curLev+1,res);  
     helper(root.left,curLev+1,res);  
   }