problem link:[Leetcode](https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/)↵
↵
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;↵
}↵
~~~~~↵
↵
↵
↵
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;↵
}↵
~~~~~↵
↵
↵
