BFS: Binary Tree Right Side View

Binary Tree Right Side View

Solved 

Medium

You are given the root of a binary tree. Return only the values of the nodes that are visible from the right side of the tree, ordered from top to bottom.

Example 1:

Input: root = [1,2,3]

Output: [1,3]

Copy

Example 2:

Input: root = [1,2,3,4,5,6,7]

Output: [1,3,7]

Copy

Constraints:

• 0 <= number of nodes in the tree <= 100
• -100 <= Node.val <= 100

# 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

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []

        res = []
        q = deque([root])

        while len(q)>0:
            sub = []
            for _ in range(len(q)):
                node = q.popleft()
                sub.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            res.append(sub[-1]) # sub 에서 마지막 값만 추가

        return res