Given a binary tree, return the vertical order traversal of its nodes values.
For each node at position (X, Y), its left and right children respectively will be at positions (X-1, Y-1) and (X+1, Y-1).
Running a vertical line from X = -infinity to X = +infinity, whenever the vertical line touches some nodes, we report the values of the nodes in order from top to bottom (decreasing Y coordinates).
If two nodes have the same position, then the value of the node that is reported first is the value that is smaller.
Return an list of non-empty reports in order of X coordinate. Every report will have a list of values of nodes.
class Solution { public: vector<vector<int>> verticalTraversal(TreeNode* root) { map<int,map<int,vector<int>>> mp; vector<vector<int>> ret; helper(root, 0, 0, mp); for(auto it=mp.begin(); it!=mp.end(); it++){ vector<int> a; for(auto iit=it->second.rbegin(); iit!=it->second.rend(); iit++) { vector<int> tmp = iit->second; sort(tmp.begin(), tmp.end()); for(auto x : tmp) a.push_back(x); } ret.push_back(a); } return ret; } void helper(TreeNode* root,int x,int y, map<int,map<int,vector<int>>>& mp){ if(!root) return; mp[x][y].push_back(root->val); helper(root->left, x-1, y-1, mp); helper(root->right, x+1, y-1, mp); } };
LC 987. Vertical Order Traversal of a Binary Tree
原文：https://www.cnblogs.com/ethanhong/p/10350073.html