Imagine standing on the right side of a binary tree and looking at it. Given its root, return the values of the nodes you can see, ordered from top to bottom. On each level you see only the rightmost node.
Example 1
Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]
Example 2
Input: root = [1,2,3,4,null,null,null,5]
Output: [1,3,4,5]
Level 2 and level 3 have nothing on the right side, so the left nodes 4 and 5 are visible.
Constraints
- The number of nodes is in the range 0 to 100
- -100 <= Node.val <= 100
Hints
Frequently asked at: Meta, Amazon, Bloomberg, Microsoft
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
A first guess is to keep following right children from the root, but that fails whenever a left subtree is deeper than the right one (see the second example). What we really want is "the last node on each level", and level order BFS gives us the levels directly. While processing a level of known size, the node at index size - 1 is the visible one.
Algorithm
- If
rootis null, return[]. Putrootin a queue. - For each level, read
size = len(queue). - Pop
sizenodes, pushing their children; wheni == size - 1, append that node's value. - Return the collected values.
Time:
O(n)Space: O(w), the maximum width of the treeInterview tip: Interviewers may ask for the left side view next; it is the same code taking the node at index 0. With the DFS version, just visit left before right.
class Solution: def rightSideView(self, root: Optional[TreeNode]) -> List[int]: if not root: return [] res = [] queue = deque([root]) while queue: size = len(queue) for i in range(size): node = queue.popleft() if i == size - 1: res.append(node.val) # rightmost node of this level if node.left: queue.append(node.left) if node.right: queue.append(node.right) return resCtrl + Enter runs the examples