199.Binary_Tree_Right_Side_View_(Medium).md

199. Binary Tree Right Side View (Medium)

Date and Time: Jun 7, 2024, 10:37 AM (EST)

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

Question:

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.

Example 1:

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

Output: [1, 3, 4]

Example 2:

Input: root = [1, null, 3]

Output: [1, 3]

Example 3:

Input: root = [ ]

Output: [ ]

KeyPoints:

We use deque() to store the root first then its root.left, root.right, we use qLen to make sure we only loop over all the nodes in each level each time. By doing that, we set node = deque.left() so until the end of the for loop, it is guarantee that this node is the right-most in that level, so if the node is not null, we can append it to res.

My Solution:

# 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]:
        # Run BFS on each level, and only append the last node on each level to res[]

        # TC: O(n), n is total nodes, SC: O(n)
        deque = collections.deque([root])
        res = []
        while deque:
            for _ in range(len(deque)):
                node = deque.popleft()
                if node:
                    if node.left:
                        deque.append(node.left)
                    if node.right:
                        deque.append(node.right)
            if node:
                res.append(node.val)
        return res

Time Complexity: $O(n)$
Space Complexity: $O(n)$