LC 0199 [M] Binary Tree Right Side View - ALawliet/algorithms GitHub Wiki

level-order traversal BFS and just append the rightmost [-1] node at each level

---

class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        if not root: return [] # remember the empty case
        res = []
        
        Q = deque([root])
        while Q:
            level = []

            for _ in range(len(Q)):
                node = Q.popleft()
                
                level.append(node.val)
                
                if node.left:
                    Q.append(node.left)
                if node.right:
                    Q.append(node.right)
                    
            res.append(level[-1])
            
        return res

you actually don't need to store the whole level because the rightmost is always the last one the queue, which is the last one in the level in each iteration of the for loop

class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        if not root: return []
        res = []
        Q = deque([root])
        while Q:
            last_val = None
            for _ in range(len(Q)):
                node = Q.popleft()
                last_val = node.val
                if node.left:  Q.append(node.left)
                if node.right: Q.append(node.right)
            res.append(last_val)
        return res