Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * Definition for a binary tree node.
- * struct TreeNode {
- * int val;
- * TreeNode *left;
- * TreeNode *right;
- * TreeNode() : val(0), left(nullptr), right(nullptr) {}
- * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
- * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
- * };
- */
- class Solution {
- public:
- vector<vector<int>> verticalTraversal(TreeNode* root) {
- if(root==nullptr) return {};
- unordered_map<int, vector<int>> xToVector;
- queue<pair<TreeNode*, int>> q;
- q.push({root, 0});
- int leftBoundary = INT_MAX; int rightBoundary = INT_MIN;
- pair<TreeNode*, int> temp;
- unordered_map<int, set<int>> formedSoFar;
- int l_leftBoundary = INT_MAX, l_rightBoundary = INT_MIN;
- while(!q.empty()){
- int qSize = q.size();
- while(qSize--){
- //all these temp's have same y coordinate
- temp = q.front(); q.pop();
- l_leftBoundary = min(l_leftBoundary, temp.second);
- l_rightBoundary = max(l_rightBoundary, temp.second);
- if((temp.first)->left != nullptr){
- q.push({(temp.first)->left, temp.second-1});
- }
- if((temp.first)->right != nullptr){
- q.push({(temp.first)->right, temp.second+1});
- }
- formedSoFar[temp.second].insert((temp.first)->val);
- }
- leftBoundary = min(leftBoundary, l_leftBoundary);
- rightBoundary = max(rightBoundary, l_rightBoundary);
- for(int i=l_leftBoundary; i<=l_rightBoundary; i++){
- for(auto &vl: formedSoFar[i]){
- xToVector[i].push_back(vl);
- }
- }
- formedSoFar.clear();
- }
- //cout << leftBoundary << " " << rightBoundary << endl;
- vector<vector<int>> answer;
- for(int i=leftBoundary; i<=rightBoundary; i++){
- if(xToVector.count(i)){
- answer.push_back(xToVector[i]);
- }
- }
- return answer;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement