aboutsummaryrefslogtreecommitdiff
path: root/vertical_order_bst.cpp
blob: e8bf5bf1651a2a4c5b98526e764cafeba9aff041 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include "leetcode.h"

class Solution {
public:
  vvd(int) verticalTraversal(TreeNode *root) {
    map<int, map<int, multiset<int>>> mmm;
    queue<pair<TreeNode *, pair<int, int>>> qpp;
    qpp.push({root, {0, 0}});
    while (!qpp.empty()) {
      auto p = qpp.front();
      qpp.pop();
      TreeNode *node = p.first;
      int x = p.second.first, y = p.second.second;
      mmm[x][y].insert(node->val);
      if (node->left)
        qpp.push({node->left, {x - 1, y + 1}});
      if (node->right)
        qpp.push({node->right, {x + 1, y + 1}});
    }
    vvd(int) ans;
    for (auto q : mmm) {
      vector<int> col;
      for (auto p : q.second)
        col.insert(col.end(), p.second.begin(), p.second.end());
      ans.push_back(col);
    }
    return ans;
  }
};