Untitled

 avatar
user_5356243
c_cpp
7 months ago
1.3 kB
9
Indexable
Never
#include<iostream>
#include<queue>
#include<vector>
#include<map>
#include<set>

using namespace std;

class Node {
    public:
        int data;
        Node* left;
        Node* right;

        Node(int data){
            this->data = data;
            left = NULL;
            right = NULL;
        }
};

vector<vector<int>> verticalTraversal(Node* root) {
    vector<vector<int>> ans;
    queue<pair<Node*, pair<int, int>> q; // {Node --> {row, col}}
    q.push({root, {0, 0}});

    map<int, map<int, multiset<int>>> mp; // col --> {row, multiset}

    while(!q.empty()){
        auto qnode = q.front();
        Node* frontNode = qnode.first;
        int row = qnode.second.first;
        int col = qnode.second.second;

        mp[col][row].insert(frontNode->data);

        if(frontNode->left) q.push({frontNode->left, {row + 1, col - 1}});
        if(frontNode->right) q.push({frontNode->right, {row + 1, col + 1}});
    }

    for(auto it: mp){
        auto colIt = it.second;
        vector<int> vertLine;
        for(auto colMapIt: colIt){
            auto mlset = colMapIt.second;

            vertLine.insert(vertLine.end(), mlset.begin(), mlset.end());
        }
        ans.push_back(vertLine);
    }
    
    return ans;
}