diff options
Diffstat (limited to 'vertical_order_bst.cpp')
-rw-r--r-- | vertical_order_bst.cpp | 29 |
1 files changed, 29 insertions, 0 deletions
diff --git a/vertical_order_bst.cpp b/vertical_order_bst.cpp new file mode 100644 index 0000000..e8bf5bf --- /dev/null +++ b/vertical_order_bst.cpp @@ -0,0 +1,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; + } +}; |