Untitled
user_5356243
c_cpp
2 years ago
1.3 kB
11
Indexable
#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; }
Editor is loading...