199. Binary Tree Right Side View

Problem Statement

link: LeetCode.cn LeetCode

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:

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

Input: root = [1,null,3] Output: [1,3]

Input: root = [] Output: []

Solution Approach

Algorithm

Complexity

time complexity: O(n) space complexity: O(n)

Implement

    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]:
        q = [root] #1
        res = []
        if not root:
            return res
        while q: #[2,3]
            temp = []  #[]
            res.append(q[-1].val) #[1,3]
            for n in q: 
                if n.left:
                    temp.append(n.left)
                if n.right:
                    temp.append(n.right) #[2,3]
            q = temp
        return res

    
    

Twitter  facebook  Email