471. View From the Right
The crown of an old oak is modelled as a binary tree: the topmost branch is root, and every branch forks into at most a left and a right branch one level lower. A photographer stands to the right of the tree and looks straight at it. At each depth the photographer can see only the right-most branch that exists at that depth, because everything further left on the same level is hidden behind it. A left branch can still be visible when the right side of the tree does not reach that deep.
Given root, return the values of the visible branches ordered from the top level to the bottom level, one value per level. If root is empty, return an empty list.
Example 1
- Input:
- root = [8,3,11,1,6,null,14,null,null,5,7]
- Output:
- [8,11,14,7]
- Explanation:
The right-most node of every level is the visible one, which gives [8,11,14,7].
Example 2
- Input:
- root = [4,9,null,2,null,7]
- Output:
- [4,9,2,7]
- Explanation:
The right-most node of every level is the visible one, which gives [4,9,2,7].
Example 3
- Input:
- root = [20,-5,30]
- Output:
- [20,30]
- Explanation:
The right-most node of every level is the visible one, which gives [20,30].
Constraints
0 ≤ number of nodes ≤ 105
-1000 ≤ Node.val ≤ 1000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)