Taking last on the queue from each level, BFS


  • 1
    A

    Since this is slightly different than how others do BFS, I put it here. The twist is just I don't check size but take the last of each level. (Still looks tedious after seeing @zwangbo's elegant solution)

    public List<Integer> rightSideView(TreeNode root) {
           LinkedList<Integer> rightView = new LinkedList<Integer>();
           if(root == null) return rightView;
           
           LinkedList<TreeNode> curLevel = new LinkedList<>();
           curLevel.add(root);
           
           while(!curLevel.isEmpty()){
               
               LinkedList<TreeNode> nextLevel = new LinkedList<>();
               TreeNode last = null;
               
               while(!curLevel.isEmpty()){
                   last = curLevel.remove();
                   if(last.left != null) nextLevel.add(last.left);
                   if(last.right != null) nextLevel.add(last.right);
               }
               
               // RightView is the last one on the queue at this level. 
               rightView.add(last.val); 
               curLevel = nextLevel;
           }
           
           return rightView;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.