199. Binary Tree Right Side View

Description:

Given the root of 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.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

'''
[1] BFS)

idea::
by bfs, there is last element in queue at every step. it will be seen on the right side view

code::
(below)

-T/C: O(n)
-S/C: O(n) # queue

'''

from collections import deque
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        ans=[]
        
        # when root is null
        if not root:
            return ans
        
        # init
        queue=deque()
        queue.append(root)
        
        # bfs
        while queue:
            size=len(queue)
            
            tmp=[]
            for i in range(size):
                cur=queue.popleft()
                tmp.append(cur.val)
                
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
            ans.append(tmp[-1])
            
        return ans