力扣987——二叉树的垂序遍历
虽然是困难，但并不复杂；
遍历二叉树，获得每个点的行列和值，然后按规则排序即可；
可以用map自动升序处理每个列；
对每列按规则排序后输出答案；
/*** 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:map<int, vector<pair<int, int>>> arr;void dfs(TreeNode* root, int hang, int lie) {arr[lie].push_back({hang, root->val});if(root->left) dfs(root->left, hang + 1, lie - 1);if(root->right) dfs(root->right, hang + 1, lie + 1);}vector<vector<int>> verticalTraversal(TreeNode* root) {dfs(root, 0, 0);vector<vector<int>> ans;for(auto& [_, now] : arr) {sort(now.begin(), now.end());vector<int> tmp;for(auto a : now) tmp.push_back(a.second);ans.push_back(tmp);}return ans;}};