The problem
Imagine standing to the right of a binary tree. Given its root, return the values of the nodes you can see, from top to bottom.
Examples
01
- Input
root = [1, 2, 3, null, 5, null, 4]
- Output
[1, 3, 4]
02
- Input
root = [1, 2, 3, 4, null, null, null, 5]
- Output
[1, 3, 4, 5]
03
- Input
root = [1, null, 3]
- Output
[1, 3]
Constraints
- 0 ≤ number of nodes ≤ 100
- −100 ≤ Node.val ≤ 100
The idea
On each level, you see exactly one node: the rightmost. It need not be a right child — if the right side of the tree is short, a node from the left shows through below it.
So go level by level, as in Level Order Traversal, and keep only the last node of each level.
- Time
- O(n)
- Space
- O(w) — the widest level
Solution · every language run against every case
class Solution: def rightSideView(self, root: Optional[TreeNode]) -> List[int]: out = [] queue = deque([root] if root else []) while queue: out.append(queue[-1].val) # the rightmost node of this level for _ in range(len(queue)): node = queue.popleft() if node.left: queue.append(node.left) if node.right: queue.append(node.right) return out