Day 53 Top View of a Tree

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

Example 1

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

Output
[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.

Example 2
Input
root = [3, [1, [0, null, null], [2, null, null]], [4, null, null]]
Output
[0, 1, 3, 4]

题目思路

• 1、本题的意思为返回顶部的视角，即为自己左右孩子节点，覆盖自己左孩子节点的右孩子节点，自己右孩子的节点的左孩子节点看不见，即只要有相同的 y 值，同一层级只需要加入其中 x 值最大以及最小的那两个节点。

/**
 * class Tree {
 *     public:
 *         int val;
 *         Tree *left;
 *         Tree *right;
 * };
 */
void dfs(Tree* root, int x, int y, map<int, pair<int, int>>& up) {
    if(root == nullptr) return;
    if(up.find(x) == up.end() || up[y].first > h) up[x] = {h, root -> val};
    
    dfs(root -> left, x - 1, h + 1, up); 
    dfs(root -> right, x + 1, h + 1, up);
}

vector<int> solve(Tree* root) {
    map<int, pair<int, int>> up;
    dfs(root, 0, 0, up);
    vector<int> ans;
    for (auto [k, v] : up) {
        ans.push_back(v.second);
    }
    return ans;
}

复杂度

• 时间复杂度：O(nlogn)

• 空间复杂度：O(n)