Top View of Binary Tree
MediumP2Coding
Imagine looking at a binary tree from above. Give each node a horizontal distance: the root is 0, a left child is one less than its parent, and a right child is one more. The top view contains, for each horizontal distance, the node that is visible from above.
Return the values of the top view from the smallest horizontal distance to the largest. When several nodes share a horizontal distance, the visible one is the one nearest the root; if two are equally near, the one that comes first in left-to-right level order. An empty tree returns [].
Example 1
- Input
- root = [1,2,3,null,4,null,5,null,null,null,6]
- Output
- [2,1,3,5,6]
Example 2
- Input
- root = [10,20,30,40,60,90,100]
- Output
- [40,20,10,30,100]
- Why
- Horizontal distances are 40:-2, 20:-1, 10:0, 30:1, 100:2. Nodes 60 and 90 also sit at distance 0 but are lower than 10.
Constraints
- 0 <= number of nodes <= 10^4
- -10^4 <= Node.val <= 10^4
Hints
Give it a real attempt first. Run shows which examples fail.
Saved automatically
Run checks the 3 visible tests, Submit all 9. ⌘Enter runs, ⌘⇧Enter submits.