Advertisement
HjHimansh

Vertical Traversal - Tree

Aug 7th, 2020
1,858
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     vector<vector<int>> verticalTraversal(TreeNode* root) {
  15.         if(root==nullptr)   return {};
  16.         unordered_map<int, vector<int>> xToVector;
  17.        
  18.         queue<pair<TreeNode*, int>> q;
  19.         q.push({root, 0});
  20.         int leftBoundary = INT_MAX; int rightBoundary = INT_MIN;
  21.        
  22.         pair<TreeNode*, int> temp;
  23.        
  24.         unordered_map<int, set<int>> formedSoFar;
  25.         int l_leftBoundary = INT_MAX, l_rightBoundary = INT_MIN;      
  26.        
  27.         while(!q.empty()){
  28.             int qSize = q.size();
  29.             while(qSize--){
  30.                 //all these temp's have same y coordinate
  31.                 temp = q.front(); q.pop();
  32.            
  33.                
  34.                 l_leftBoundary = min(l_leftBoundary, temp.second);
  35.                 l_rightBoundary = max(l_rightBoundary, temp.second);
  36.            
  37.                 if((temp.first)->left != nullptr){
  38.                     q.push({(temp.first)->left, temp.second-1});
  39.                 }
  40.                 if((temp.first)->right != nullptr){
  41.                     q.push({(temp.first)->right, temp.second+1});
  42.                 }
  43.                 formedSoFar[temp.second].insert((temp.first)->val);
  44.                
  45.             }
  46.             leftBoundary = min(leftBoundary, l_leftBoundary);
  47.             rightBoundary = max(rightBoundary, l_rightBoundary);
  48.            
  49.             for(int i=l_leftBoundary; i<=l_rightBoundary; i++){
  50.                 for(auto &vl: formedSoFar[i]){
  51.                     xToVector[i].push_back(vl);
  52.                 }
  53.             }
  54.        
  55.             formedSoFar.clear();
  56.         }
  57.         //cout << leftBoundary << " " << rightBoundary << endl;
  58.         vector<vector<int>> answer;
  59.        
  60.         for(int i=leftBoundary; i<=rightBoundary; i++){
  61.             if(xToVector.count(i)){
  62.                 answer.push_back(xToVector[i]);
  63.             }    
  64.         }
  65.        
  66.         return answer;
  67.        
  68.     }
  69. };
Advertisement
RAW Paste Data Copied
Advertisement