【Day 53 】2024-05-30 - Top-View-of-a-Tree

[azl397985856]

Top-View-of-a-Tree

入选理由

暂无

题目地址

https://binarysearch.com/problems/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

[Dtjk]

class Solution { public:

typedef map<int, multiset<pair<int, int>>> MAP;

void dfs(int x, int y, TreeNode* root, MAP &mp) {
    if (!root) return ;
    mp[y].insert({x, root->val});
    dfs(x + 1, y - 1, root->left, mp);
    dfs(x + 1, y + 1, root->right, mp);
}

vector<vector<int>> verticalTraversal(TreeNode* root) {
    MAP mp;
    dfs(0, 0, root, mp);
    vector<vector<int>> ans;
    for (auto &[a, b] : mp) {
        vector<int> temp;
        for (auto &e : b) {
            temp.push_back(e.second);
        }
        ans.push_back(temp);
    }
    return ans;
}

};