You get the root of a binary tree. Imagine you stand to its right and look at it. Return the values you can see, from the top row down.
On each row, you see only the node farthest to the right. It hides the others. If the right side is shorter, lower rows show nodes from the left side. For an empty tree, return an empty array.
In the examples, each tree is written row by row from the top. Each row goes left to right. null marks a missing child.
Example 1:
6
/ \
3 8
/ /
2 7
Input: root = [6,3,8,2,null,7]
Output: [6,8,7]
Explanation: The last node of each row is 6, then 8, then 7.
The 3 and the 2 hide behind them.
Example 2:
5
/ \
9 2
\
4
/
7
Input: root = [5,9,2,null,4,null,null,7]
Output: [5,2,4,7]
Explanation: The right side ends at 2.
Further down, 4 and 7 are alone on their rows.
So you see them, even though they sit under 9.
Constraints:
- The tree has 0 to 100 nodes.
- Each value is a whole number from -100 to 100.
- A value can appear more than once.
Note:
The tutorial walks the tree level by level with a queue. The queue starts with the root. At the start of each round it holds exactly one level: count its nodes, take them out one by one from the front, and put each node's children (left, then right) at the back, where they wait for the next round. The last node taken out in a round is the rightmost node of its level: that is the one you see.
Each node enters and leaves the queue once, so the time is O(n) for a tree of n nodes. The queue holds at most about two levels at a time, which is O(n) extra space in the worst case.
Free plan: 30 tutor messages. PRO is unlimited.
