You are given root, the root of a binary tree (or nothing, for an empty tree).
Imagine standing to the right of the tree and looking at it: on each level, you see only the
rightmost node. Return the values you see, from the top level down. An empty tree gives [].
Trees are written in level order, row by row from the top, with null where a node is missing:
[4, 2, 7, null, 3] is 4 at the root, 2 and 7 below it, and 3 as the right child of 2.
Example 1
- Input
- root = [8, 4, 9, 2, 6]
- Output
- [8, 9, 6]
Example 2
- Input
- root = [1, 2, 3, 4]
- Output
- [1, 3, 4]
Constraints
- The tree holds 0 to 2000 nodes.
- Every value is between −1000 and 1000.
Show the pattern
Trees
What you see from the right is the last node on each level, so go level by level (breadth-first) and keep each level's final value.
See trees in a visualiserShow the approach
Go breadth-first, one level at a time. Keep the list of nodes on the current level, starting with just the root. Each round, record the value of the level's last node, then build the next level from the children, left child before right child, node by node. Stop when a level is empty.
The rightmost node of a level isn't always a right child: when a level has a single node, you see it whichever side it hangs from.
Time: O(n) · Space: O(w), w the widest level