Advertisement
leoanjos

Vertical Order Traversal of a Binary Tree

May 26th, 2022
816
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.         multiset<tuple<int, int, int>> order;
  16.        
  17.         queue<tuple<TreeNode*, int, int>> q;
  18.         q.emplace(root, 0, 0);
  19.        
  20.         while (!q.empty()) {
  21.             auto [node, row, col] = q.front();
  22.             q.pop();
  23.            
  24.             order.emplace(col, row, node->val);
  25.             if (node->left != nullptr) {
  26.                 q.emplace(node->left, row + 1, col - 1);
  27.             }
  28.            
  29.             if (node->right != nullptr) {
  30.                 q.emplace(node->right, row + 1, col + 1);
  31.             }
  32.         }
  33.        
  34.         int last = INT_MIN;
  35.         vector<int> curr;
  36.         vector<vector<int>> ans;
  37.        
  38.         for (auto [col, row, v]: order) {
  39.             if (col > last) {
  40.                 if (!curr.empty()) {
  41.                     ans.push_back(curr);
  42.                 }
  43.                
  44.                 last = col;
  45.                 curr.clear();
  46.             }
  47.            
  48.             curr.push_back(v);
  49.         }
  50.        
  51.         if (!curr.empty()) {
  52.             ans.push_back(curr);
  53.         }
  54.        
  55.         return ans;
  56.     }
  57. };
Advertisement
RAW Paste Data Copied
Advertisement