diff options
Diffstat (limited to 'other/vertical_order_bst.cpp')
-rw-r--r-- | other/vertical_order_bst.cpp | 29 |
1 files changed, 29 insertions, 0 deletions
diff --git a/other/vertical_order_bst.cpp b/other/vertical_order_bst.cpp new file mode 100644 index 0000000..a429d4d --- /dev/null +++ b/other/vertical_order_bst.cpp @@ -0,0 +1,29 @@ +#include "leetcode.h" + +class Solution { +public: + vvd 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 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; + } +}; |