Top View of a Tree

Given a binary tree root, return the top view of the tree, sorted left-to-right.

Constraints

• n ≤ 100,000 where n is the number of nodes in root

https://binarysearch.com/problems/Top-View-of-a-Tree

Examples

Example 1

Input

• root =

Output

• answer = [0, 1, 3, 4]

Example 2

Input

• root =

Output

• answer = [2, 1, 3, 6, 7]

Explanation

Note that directly above 4 is 1 and directly above 5 is 3 so these are not part of the top view.

Solution