/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<vector<int>> verticalTraversal(TreeNode* root) { vector<vector<int>> v; if(!root) return v; map<int, map<int, vector<int>>> mp; queue<pair<TreeNode*, pair<int,int>>>q; q.push({root, {0,0}}); while(!q.empty()) { auto f=q.front(); q.pop(); int p8=f.first->val; int hdfo=f.second.first; int dfo=f.second.second; mp[hdfo][dfo].push_back(p8); if(f.first->left) q.push({f.first->left, {hdfo-1, dfo+1}}); if(f.first->right) q.push({f.first->right, {hdfo+1, dfo+1}}); } for(auto i:mp) { vector<int> v2; for(auto j:i.second) { sort(j.second.begin(), j.second.end()); for(auto k:j.second) { v2.push_back(k); } } v.push_back(v2); } return v; } };
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter