Leetcode 199 Binary Tree Right Side View (Medium)

Subscribe to my newsletter and never miss my upcoming articles

Question Link : https://leetcode.com/problems/binary-tree-right-side-view/

It is pretty simple explanation if you visualize the tree .If we do level order traversal and keep each level node values in a list (keeping from left to right) the last value in the list needs to be added to result as that is the only one which will be seen from right side view. In case of the left side view it will be the first value in list of node for the level or if we keep nodes from right to left it will still be the last node value of each level.

Since in this question we have right side view , lets see the list content per level for the given sample in the question

Input: [1,2,3,null,5,null,4]

Output: [1, 3, 4]

Explanation:

   1            <--- Level 1
 /   \
2     3         <--- Level 2
 \     \
  5     4       <--- Level 3

Content of the level wise value will be
Level  1 -> [1]
Level  2-> [2,3]
Level  3 -> [5,4]

The last value of each level needs to be added for result view.

Now we can simply write a Level Order Traversal using Queue


class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res=new ArrayList<>();
        List<Integer> level=new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        if(root==null) return res;
        q.offer(root);
        q.offer(null);
        while(!q.isEmpty()){
            TreeNode tmp= q.poll();
             if(tmp!=null){
                 level.add(tmp.val);

                 if(tmp.left!=null)
                    q.offer(tmp.left);
                if(tmp.right!=null)
                q.offer(tmp.right);

            }else{
                if(level.size()>0)
                    res.add(level.get(level.size()-1));
                 level.clear();
                if(!q.isEmpty())
                    q.offer(null);
            }
        }

    return res;
    }
 }

No Comments Yet