problem link:Leetcode

problem:Given a binary tree, return the vertical order traversal of its nodes values.

This approah is using unorederd_map and i think it is nlog(n) due to n for loop and log(n) for find operation in it.Is it correct?

Traverse the tree tracking x and y coordinates, and populate m[x][y] with values. Note that we use set to hold multiple values and sorts them automatically.

Then, we iterate x [-999, 999] and y [0, 999] and populate our answer. Since the tree size is limited to 1000, our coordinates will be within these intervals.

unordered_map<int, unordered_map<int, set<int>>> m;
void traverse(TreeNode* r, int x, int y) {
  if (r != nullptr) {
    m[x][y].insert(r->val);
    traverse(r->left, x - 1, y + 1);
    traverse(r->right, x + 1, y + 1);
  }
}
vector<vector<int>> verticalTraversal(TreeNode* r) {
  vector<vector<int>> res;
  traverse(r, 0, 0);
  for (int x = -999; x < 1000; ++x) {
    auto it = m.find(x);
    if (it != end(m)) {
      res.push_back(vector<int>());
      for (int y = 0; y < 1000; ++y) {
        auto ity = it->second.find(y);
        if (ity != end(it->second)) {
          res.back().insert(end(res.back()), begin(ity->second), end(ity->second));
        }
      }
    }
  }
  return res;
}

This approach is using map ,I don't know time complexity of this one

We could also use map[x, map[y, set[val]]], and it will simplify the code a bit:

void dfs(TreeNode* r, int x, int y, map<int, map<int, set<int>>> &m) {
  if (r != nullptr) {
    m[x][y].insert(r->val);
    dfs(r->left, x - 1, y + 1, m);
    dfs(r->right, x + 1, y + 1, m);
  }
}
vector<vector<int>> verticalTraversal(TreeNode* r, vector<vector<int>> res = {}) {
  map<int, map<int, set<int>>> m;
  dfs(r, 0, 0, m);
  for (auto itx = m.begin(); itx != m.end(); ++itx) {
      res.push_back(vector<int>());
      for (auto ity = itx->second.begin(); ity != itx->second.end(); ++ity) {
          res.back().insert(end(res.back()), begin(ity->second), end(ity->second));
      }
  }
  return res;
}