Top View of a Tree#

1
Given a binary tree root,
2

3
 return the top view of the tree, sorted left-to-right.
4

5
Constraints
6

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

9
Example 1
10

11
Input
12
root = [1, [2, null, [4, null, [5, null, [6, null,
13
       [7, null, null]]]]], [3, null, null]]
14

15
Output
16
[2, 1, 3, 6, 7]
17

18
Explanation
19

20
Note that directly above 4 is 1 and directly above 5 is 3
21

22
so these are not part of the top view.
23

24
Example 2
25
Input
26
root = [3, [1, [0, null, null], [2, null, null]], [4, null, null]]
27
Output
28
[0, 1, 3, 4]

1
/**
2
 * class Tree {
3
 *     public:
4
 *         int val;
5
 *         Tree *left;
6
 *         Tree *right;
7
 * };
8
 */
9
void dfs(Tree* root, int x, int y, map<int, pair<int, int>>& up) {
10
    if(root == nullptr) return;
11
    if(up.find(x) == up.end() || up[y].first > h) up[x] = {h, root -> val};
12

13
    dfs(root -> left, x - 1, h + 1, up);
14
    dfs(root -> right, x + 1, h + 1, up);
15
}
16

17
vector<int> solve(Tree* root) {
18
    map<int, pair<int, int>> up;
19
    dfs(root, 0, 0, up);
20
    vector<int> ans;
21
    for (auto [k, v] : up) {
22
        ans.push_back(v.second);
23
    }
24
    return ans;
25
}