#173MediumTrees· Level-Order Traversal

Tree Right Side View

A cave-diving map is drawn as a binary tree: each chamber has at most a left and a right passage leading deeper. A drone is released at the entrance (the root) and films the cave **from the right side**. At each depth it sees only the rightmost chamber on that level, because anything to its left is hidden behind it. Return the values of the chambers the drone sees, ordered from the entrance downward (one value per level).

Input format

`root`: a binary tree given in level order as an array with `null` for missing children.

Output format

An array with one value per level: the value of the rightmost node on that level.

Examples

Input: root = [1, 2, 3, null, 5, null, 4]

Output: [1, 3, 4]

Level 0 shows 1, level 1 shows 3, level 2 shows 4 (5 is hidden behind 4).

Input: root = [1, 2, null, 3]

Output: [1, 2, 3]

The right side is empty on the lower levels, so the left chain 1, 2, 3 is visible.

Input: root = []

Output: []

An empty cave shows nothing.

Constraints

0 <= number of nodes <= 10^4
-100 <= node value <= 100

#tree
#breadth-first-search
#depth-first-search