acash's blog

By acash, history, 5 years ago, In English

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;
}
  • Vote: I like it
  • -3
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Are you trying to find the worst case? If yes then you are wrong. Unordered map has the best case complexity of O(1) and the worst case complexity of O(n). Map has O(logn) in both cases. And Set has the worst case complexity of O(logn). I don't think you need the full answer just consider these things and use your brain. :)

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am confused in second one map<int,map<int,set>> here

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Suppose I am using map<int, vector>. Now, look here the key is an integer. And the value is a vector. When you type in v[1].push_back(1) it works just like a normal vector push. Which has a complexity of O(1) and when you are calling v[1] in a map it is going to have a complexity of O(logn). So basically we can say it has a complexity of O(logn). Even though not precisely. When you are using map<int, set> you are basically calling the value in O(logn) and then you are performing normal set operations in that value in O(logn) time mostly. It is as simple as that. Now I hope you will be able to calculate it. :)